Title: How to determine if a binary tree is height-balanced? Source: www.geeksforgeeks.org
A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced.
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.
The above height-balancing scheme is used in AVL trees. The diagram below shows two trees, one of them is height-balanced and other is not. The second tree is not height-balanced because height of left subtree is 2 more than height of right subtree.
To check if a tree is height-balanced, get the height of left and right subtrees. Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/* http://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/ */ class HeightBalancedBTree { private boolean result = true; public boolean isBalanced(TreeNode root) { helper(root); return result; } public int helper(TreeNode root) { TreeNode node = root; if(node==null) { return 0; } int left = helper(node.left); int right = helper(node.right); if(Math.abs(left - right)>1) result = false; return Math.max(left,right)+1; } } |
Admiring the hard work you put into your website and in depth information you provide.
It’s great to come across a blog every once in a while that isn’t the same unwanted rehashed information.
Excellent read! I’ve saved your site and I’m adding your RSS feeds to my Google account.