Start learning free

LESSON 435 OF 573 · BINARY TREES

Balanced Binary Tree in Scala: O(n) with a Bottom-Up Height Check

Practice O(n) Read the full explanation

Given the root of a binary tree, return true if it is height-balanced, and false otherwise.

A binary tree is height-balanced when, at every node, the heights of its left and right subtrees differ by at most 1.

The height of a tree is the number of nodes on its longest path from the top down to a leaf. An empty tree has a height of 0, and it is balanced.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

Example 1:

    3
   / \
  9   20
     /  \
    15   7

Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: At the root, the left subtree (9) has a height of 1 and the right subtree (20, 15, 7) a height of 2: they differ by 1. At 20, both subtrees have a height of 1, and the leaves have two empty subtrees.

Example 2:

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

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: At the root, the left subtree has a height of 3 and the right subtree a height of 1: they differ by 2.

Example 3:

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

Input: root = [1,2,2,3,null,null,3,4,null,null,4]
Output: false
Explanation: The root is fine: both of its subtrees have a height of 3. But the left 2 has a left subtree of height 2 (3 and 4) and an empty right subtree, of height 0: they differ by 2. The rule must hold at every node, not only at the root.

Constraints:

The number of nodes in the tree is in the range [0, 5000].
Each node value is between -10⁴ and 10⁴.
The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Measuring a subtree's height again for every node above it repeats work. Find each subtree's height once, from the bottom up, and check the rule at the same time.

STEP 1 OF 9

Guided

Ctrl + Enter to check

SCALA · BINARY TREES

Balanced Binary Tree in Scala, explained

Problem overview

The method isBalanced receives the root of a binary tree and returns true when the tree is height-balanced: at every node, the heights of the left and right subtrees differ by at most 1. The height of a tree is the number of nodes on its longest path from the top down to a leaf, and an empty tree has height 0 and counts as balanced. The lesson provides the TreeNode class, with an Int field value and the fields left and right, which are null when a child is missing.

In the tree [3, 9, 20, null, null, 15, 7] (level order, null for a missing child), the root's left subtree is the single node 9, of height 1, and its right subtree, 20 with children 15 and 7, has height 2. They differ by 1, and every other node is fine too, so the answer is true. In [1, 2, 2, 3, 3, null, null, 4, 4], the root's left subtree has height 3 and its right subtree height 1: they differ by 2, so the answer is false.

The rule must hold at every node, not just the root. In [1, 2, 2, 3, null, null, 3, 4, null, null, 4] the root is fine, because both sides have height 3. But the left 2 has a left subtree of height 2 and an empty right subtree of height 0, so the tree is not balanced.

The lesson asks for O(n) time, visiting each node once.

Approach: compute heights from the bottom and signal a failure with -1

The direct idea calls a height function on both children of every node and compares. That works, but height itself walks a whole subtree, and it is called again for every node above it. On a long chain of nodes that is about n² work.

The fix is to find each subtree's height once, from the bottom up, and to check the rule on the way back. A recursive helper height returns the height of the tree under a node when that tree is balanced, and -1 as soon as it finds a node that breaks the rule. A real height is never negative, so -1 can't be confused with one. It means "unbalanced somewhere in here", and once it appears, it travels up through every caller unchanged.

At each node the helper does the following:

An empty tree has height 0.
Ask for the left height. If it is -1, return -1 immediately.
Ask for the right height. If it is -1, return -1.
If the two heights differ by more than 1, this node breaks the rule: return -1.
Otherwise return 1 + max(left, right): this node plus its taller side.

Then isBalanced only has to ask whether the answer for the root is not -1. Run on the three examples, height returns 3 for the first tree and -1 for the second and the third. In the first tree, height of the node 9 is 1 and height of the node 20 is 2.

Step by step

Define what isBalanced returns. It calls height(root) and answers whether the result is != -1. The helper is written next.
Write the helper's signature. height takes a TreeNode named node and returns an Int.
Handle the empty tree. If node == null, return 0. This is also what stops the recursion when it steps past a leaf.
Get the left height with a recursive call on node.left, stored in a val named leftHeight. Trust the recursion: it returns the left subtree's height, or -1.
Pass the failure up. If leftHeight == -1, return -1 at once, without looking at the right side.
Get the right height the same way, as rightHeight.
Pass the failure up again. Do not skip this check: a -1 from the right would otherwise be treated as a height, and it differs from an empty side's 0 by only 1.
Check this node. If math.abs(leftHeight - rightHeight) > 1, return -1. This line runs for every node on its way back up, so the rule is checked everywhere.
Return the height of the tree under the node: 1 for the node itself plus math.max(leftHeight, rightHeight).

The solution in Scala

class Solution {
    def height(node: TreeNode): Int = {
        if (node == null) {
            return 0
        }
        val leftHeight = height(node.left)
        if (leftHeight == -1) {
            return -1
        }
        val rightHeight = height(node.right)
        if (rightHeight == -1) {
            return -1
        }
        if (math.abs(leftHeight - rightHeight) > 1) {
            return -1
        }
        return 1 + math.max(leftHeight, rightHeight)
    }

    def isBalanced(root: TreeNode): Boolean = {
        return height(root) != -1
    }
}

The Scala details worth a closer look:

Recursive methods need a return type. height declares : Int explicitly. Scala can infer most return types, but not for a method that calls itself.
null in Scala. The lesson's TreeNode uses null for a missing child, so node == null is the base case. == compares values, and against null it is safe: it never throws.
return in a method body. Each early exit is a plain return. This is allowed anywhere in a method, and it is not inside a closure here, so Scala 3.5 doesn't warn. The last expression would work as well without the keyword.
math.abs and math.max. They come from the scala.math package object, available without an import. math.abs drops the sign, so it doesn't matter which side is taller.
A helper method in the class. height is a normal method of Solution. It's called without any prefix, and its position above or below isBalanced makes no difference.
Recursion depth. Each level of the tree adds one stack frame. The lesson limits trees to 800 levels, which is well within what the JVM allows by default. A chain of 800 nodes is handled without trouble.

Complexity

Let n be the number of nodes and h the height of the tree.

Time: O(n). Each node is visited once, and the work at a node is a few comparisons. The early returns for -1 only make it faster on unbalanced trees.

Space: O(h). The only extra memory is the recursion stack, one frame per level. That is about log n for a balanced tree and up to n for a chain.

Edge cases and common mistakes

An empty tree. null returns true: height(null) is 0, which is not -1.
A single node. Both sides have height 0, so the tree is balanced.
Chains. A root with one child is balanced, with heights 1 and 0. A chain of three nodes is not: its top node sees heights 2 and 0.
Checking only the root. The third example has a root with equal subtree heights, yet the tree is not balanced. The check inside height runs at every node.
Not handling -1 from the right. Without the rightHeight == -1 check, a failure on the right side could be mistaken for a height and give a wrong true.
Measuring height again from every node. That also gives the right answer, but it repeats work on every node above, which is the slowdown this approach avoids.

Testing

[3, 9, 20, null, null, 15, 7] gives true.
[1, 2, 2, 3, 3, null, null, 4, 4] gives false.
[1, 2, 2, 3, null, null, 3, 4, null, null, 4] gives false.
An empty tree (null) gives true.
[1] gives true.
[1, 2] gives true.
[1, 2, null, 3] (a chain of three) gives false.

Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free