Check for Balanced Tree
Given a binary tree, find if it is height balanced or not.
A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree. Expected time complexity is O(n)
Algorithm:
- Create a class to hold height and isBalanced boolean of a tree
- Traverse tree in post order
- If
node is null
thenreturn height=0 and isBalanced = true
- If node is leaf node then
return height=1 and isBalanced = true
- Recursively call for left sub tree
- Recursively call for right sub tree
- If
leftSubTree is balanced and rightSubTree is balanced
thenreturn height = Max(leftSubTree.height and leftSubTree.height) + 1 and balanced = true
- Else
return balanced = false and height =0
- If
Latest Source Code:
Github: HeightBalancedTreeChecker.java
Output:
1 / \ / \ / \ / \ 2 3 / \ / / \ / 4 5 6 / 7 Is height balanced : true ---------------------------------------------------------------------- 1 / \ / \ / \ / \ 2 3 / \ / \ 4 5 / 7 Is height balanced : false