# 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