Height balanced binary search tree
In last post, we discussed what is height of tree and how to find height of tree. In this post, we will use that information to find if tree is height balanced binary search tree or not? A tree is called as balanced tree if difference between height of left and right subtree is at most 1 at every node.So, if tree rooted at node let’s r, height of left subtree l and height of right subtree r, should not differ more than 1.
For example, below tree is balanced
where as this tree is not.
Worst case complexity of algorithms running on balanced tree is O( log N ) where as on non balanced tree it will be O(N).
How to find if tree is balanced binary search tree?
To find answer to bigger problem, we need to find that all subtrees are also balanced. Idea is to find if left and right subtree are balanced, then check if difference between height of left and right subtree is at max 1. If any of these conditions is false, tree is not balanced.
We can solve this problem using bottom up approach. Go all the way to leaf and then check if leaf node is balanced. Then return height of left and right subtree to parent and check if parent is balanced, go on till you reach root.
Algorithm to find if tree is balanced is height balanced binary search tree
1. Start from root 2. For each node of tree. 2.1 Find height of left subtree, call it lheight 2.2 Find height of right subtree, call it rheight 2.3 If difference between lheight and rheight is 1, return true 2.4 Else return false.
Height balance binary search tree check implementation
Complexity of algorithm to find if tree is height balanced binary search tree or not is O(N2) as we have to visit each node of tree at least once and find height of left and right subtree which takes O(N).
Working of algorithm can be understood easily by looking at this figure.
Optimized version will be to calculate and push height up when we are checking subtrees for balanced or not. In this case, we need to return two thing to calling function, first, whether left and right subtree are balanced and second, height of corresponding left and right subtree which will be used to decide if subtree at parent is balanced or not. Since we can return only one value from function in C, we will use a pointer to catch value of height.
Please share if there is something wrong or missing,we would love to hear from you. Sharing is caring.