Determine if a binary tree is balanced
A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ more than one.
Input : The root of a binary tree
Output : Boolean
Approach 1 :
- For a given node we will get the height of its left and right sub tree
- If the height difference is greater than one then we will return false
- We will repeat this process for each of the node in the tree using recursion
Time complexity : O (N logN)
Approach 2 :
- Minimize the number of calls to the getHeight function in the previous approach
- We can modify the getHeight function to check the current node is balanced or not
Time complexity : O (N)
To learn more about recursion refer this article.