Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution:

Recursion. Check the left and right subtrees; store the height during recursion in order to compare the subtrees.

However, the following code calls the depth() so many times, and it is inefficient.

The following version is better: every time we found that the subtree is not balanced, we could return -1 and break the recursions.

Comments

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs