Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Balanced Binary Tree

Problem Statement

Determine if a binary tree is height-balanced.

A binary tree is considered height-balanced if, for each node, the difference in height between its left and right subtrees is no more than one.

Examples:

  1. Input:
    3
   / \
  9  20
     / \
    15  7
  • Expected Output: true
  • Justification: Every node in the tree has a left and right subtree depth difference of either 0 or 1.
  1. Input:
        1
      /   \
     2     2
    / \   / \
   3   3 3   3
  / \       / \
 4   4     4   4
  • Expected Output: true

.....

.....

.....

Like the course? Get enrolled and start learning!
Bruno Ely

Bruno Ely

· 2 years ago

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

In example 2, the height difference for the two nodes with value "2" is 2. Their inner subtree has height 1, and their outer subtree has height 3.

Show 3 replies
Pritam Deshmukh

Pritam Deshmukh

· a year ago

[1,2,2,3,null,null,3,4,null,null,4] is balanced tree and should return true.

Show 1 reply