Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

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 :

Logic :

  • 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

This post is a follow-up of Create a binary search tree in javascript. I recommend reading that first, as the following code uses the method from it.

Time complexity : O (N logN)

Solution :


Approach 2 :

Logic :

  • 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)

Solution :

To learn more about recursion refer this article.


  • CTCI_6_4.4

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *