Related: LeetCode 110 - Balanced Binary Tree
Check if a given Binary Tree is height balanced like a Red-Black Tree | GeeksforGeeks
In a Red-Black Tree, the maximum height of a node is at most twice the minimum height (The four Red-Black tree properties make sure this is always followed). Given a Binary Search Tree, we need to check for following property.
For every node, length of the longest leaf to node path has not more than twice the nodes on shortest path from node to leaf.
We need to write a recursive function that returns three things, a boolean value to indicate the tree is balanced or not, minimum height and maximum height.
Check if a given Binary Tree is height balanced like a Red-Black Tree | GeeksforGeeks
In a Red-Black Tree, the maximum height of a node is at most twice the minimum height (The four Red-Black tree properties make sure this is always followed). Given a Binary Search Tree, we need to check for following property.
For every node, length of the longest leaf to node path has not more than twice the nodes on shortest path from node to leaf.
We need to write a recursive function that returns three things, a boolean value to indicate the tree is balanced or not, minimum height and maximum height.
bool isBalancedUtil(Node *root, int &maxh, int &minh){ // Base case if (root == NULL) { maxh = minh = 0; return true; } int lmxh, lmnh; // To store max and min heights of left subtree int rmxh, rmnh; // To store max and min heights of right subtree // Check if left subtree is balanced, also set lmxh and lmnh if (isBalancedUtil(root->left, lmxh, lmnh) == false) return false; // Check if right subtree is balanced, also set rmxh and rmnh if (isBalancedUtil(root->right, rmxh, rmnh) == false) return false; // Set the max and min heights of this node for the parent call maxh = max(lmxh, rmxh) + 1; minh = min(lmnh, rmnh) + 1; // See if this node is balanced if (maxh <= 2*minh) return true; return false;}// A wrapper over isBalancedUtil()bool isBalanced(Node *root){ int maxh, minh; return isBalancedUtil(root, maxh, minh);}
1) Every node has a color either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4) Every path from root to a NULL node has same number of black nodes.
Read full article from Check if a given Binary Tree is height balanced like a Red-Black Tree | GeeksforGeeks