|
This post is completed by 2 users
|
Add to List |
38. Determining Binary Tree Balance
Objective: Given a binary tree, Find if a Given Binary Tree is Balanced.
What is a balanced Tree: A balanced tree is a tree in which the difference between the heights of sub-trees of any node in the tree is not greater than one.
Example:
Naive Approach:
for each node of the tree, get the height of the left and right subtree and check the difference, if it is greater than 1, return false.
Time Complexity: O(N^2)
Better Approach: Recursion
- Post-order traversal technique
- Travel down to leaf nodes and then go up.
- while going up, calculate the left and right subtree height.
- If the difference between them is greater than 1, return -1.
- Else return Max(leftHeight, rightHeight) +1.
- Here you won't calculate the height of the subtrees by calling the function, instead, you will store the height at each level and when you go one level up, you add one to it.
- So Time complexity is O(N), Space complexity as O(h) , h = height of the tree
Output:
Is Tree Balanced : true Is Tree Balanced : false