110. Balanced Binary Tree

Problem¶

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104

Solve¶

White board¶

First, we need to understand A balance binary tree, which is a binary tree that have:

Every node in tree is a balance binary tree
Height of left node and right node difference is not greater than 1

We will want to work with height of every single node in the tree. This can be achieve by traversal and storing all tree node height using recursion,

func getHeight(root *TreeNode) int {
    left := 0
    if root.Left != nil {
        left = getHeight(root.Left)
    }
    right := 0
    if root.Right != nil {
        right := getHeight(root.Left)
    }
    return max(left, right) + 1
}

but the problem is that:

How we can store data that we can reference to the corresponded tree node

I achieved this by creating a new tree, that have the same structure of our tree, where it have another field height.

Clone tree and comparing height¶

O(n)

This clone method is quite trouble some, we really need to spend less than this much of memory for this kind of problem. As our height is only use in one comparation.

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type TreeWrap struct {
    val int
    height int
    left *TreeWrap
    right *TreeWrap
}

func wrap(tn *TreeNode) *TreeWrap{
    if tn == nil {
        return nil
    }
    height := 1
    var left *TreeWrap = nil
    if tn.Left != nil {
        left = wrap(tn.Left)
        height = max(height, 1 + left.height)
    }
    var right *TreeWrap= nil
    if tn.Right != nil {
        right = wrap(tn.Right)
        height = max(height, 1 + right.height)
    }

    tw := &TreeWrap{
        tn.Val,
        height,
        left,
        right,
    }
    return tw
}

func (tw *TreeWrap) isBalanced() bool {
    if tw == nil {
        return true
    }
    left := 0
    if tw.left != nil {
        if ! tw.left.isBalanced() {
            return false
        }
        left = tw.left.height
    }

    right := 0
    if tw.right != nil {
        if ! tw.right.isBalanced() {
            return false
        }
        right = tw.right.height
    }

    return left - right <= 1 && left - right >= -1
}

func isBalanced(root *TreeNode) bool {
    rootwrap := wrap(root)
    return rootwrap.isBalanced()
}

Optimize 1 - Only traversal once and not storing height¶

O(n)

Last update : September 28, 2023
Created : September 28, 2023