Leetcode solution 110: Balanced Binary Tree

Problem Statement 

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.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

As described in the problem, it is intuitive to solve this problem recursively, especially given this is a tree related problem. What we can do is get the height of the left sub tree, compared with the right sub tree, then do the logics to see if it’s balanced or not. If at certain level either the left or right sub tree is not balanced, then entire Tree is not balanced. Classic usage for post order traversal.

Solutions

Post order traversal using recursion

Calculate the height of the left subtree, calculate the height of the right subtree, then compare. If it's already not balanced, return -1 and directly return

Time Complexity: O(N), N is the total tree nodes since it is visited once and only once
Space Complexity: O(1), No extra space is needed

References

• Leetcode discussion