Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left and the right sub-trees is at most 1 at any node.
Consider the following examples
1 1 1 1
/ /
2 3 2 2 2
/
3
Balanced Balanced Balanced Unbalanced
Solution:
We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).
Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it.
We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.
Here is the C++ implementation of this algorithm. It runs in O(n) time.
We say that a binary tree is balanced if height difference of left and the right sub-trees is at most 1 at any node.
Consider the following examples
1 1 1 1
/ /
2 3 2 2 2
/
3
Balanced Balanced Balanced Unbalanced
Solution:
We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).
Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it.
We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.
Here is the C++ implementation of this algorithm. It runs in O(n) time.