Height Balanced Binary Tree

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.