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.
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.
0and a leaf node is ALWAYS BALANCED.
tupleor an object of
TreeInfoclass that will have
isBalanced = trueand
height = -1
leftSubtreeInfoby recursive approach - calling the same function again with
rightSubtreeInfoby recursive approach - calling the same function again with
leftBalanced && rightBalanced && absolute(leftHeight - height) <=1.
maximum(leftHeight, rightHeight) + 1
O(n)- Time complexity because we have to traverse all the nodes of the tree at max.
O(h)- Space complexity.