Height Balanced Binary Tree

Given a pointer to the root node of a binary tree, return true if the binary tree is height-balanced. A height-balanced binary tree is a Binary tree in which the difference between the left subtree height and the right subtree height is at most 1. Height of a binary tree is the number of edges between the root node to the longest leaf node.

Solution - Recursive approach

A height balanced binary tree is nothing but a binary tree where the difference in heights of the left subtree and right subtree is atmost 1.

Here, we are going to go at the absolute leaf nodes (at the end of the tree) and return some information from there. We are essentially going to bubble up information in order to determine if the tree is height balanced.

  1. Create an object / class / helper function to determine two features: isBalanced and height.
  2. The height of the leaf node is always 0 and a leaf node is ALWAYS BALANCED.
  3. The base case will be when there is no tree, from there we will return a tuple or an object of TreeInfo class that will have isBalanced = true and height = -1
  4. We then calculate leftSubtreeInfo by recursive approach - calling the same function again with tree.left.
  5. We then calculate rightSubtreeInfo by recursive approach - calling the same function again with tree.right.
  6. The meaty condition here to check if the left subtree and right subtree are balanced is we check if leftBalanced && rightBalanced && absolute(leftHeight - height) <=1.
  7. If the above condition is satisfied, the subtree is balanced. We then calculate the height of the binary tree by maximum(leftHeight, rightHeight) + 1
  8. At the end, we return the tuple.

Time and Space complexity:

  • O(n) - Time complexity because we have to traverse all the nodes of the tree at max.
  • O(h) - Space complexity.
Solve Height Balanced Binary Tree on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn