Balance a Binary Search Tree

Medium Trees & BST BST Basics Original on LeetCode

Reported atMeta

Balance a Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern. The best approach, optimal (in-order nodes + relink), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from sorted values + new tree up.

Problem

You are given the root of a binary search tree. Return a height-balanced binary search tree that contains exactly the same values.

A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most 1. If more than one balanced tree is possible, any of them is accepted.

Examples

Example 1

Input
root = [2, 1, 3, null, null, null, 4, null, 5]
Output
[3, 1, 4, null, 2, null, 5]
Why
The right spine 2 -> 3 -> 4 -> 5 makes the tree 4 levels deep. Rooting at the middle value 3 gives a tree of height 3 where no node's subtrees differ by more than 1. Other balanced shapes, such as [3, 2, 4, 1, null, null, 5], are accepted too.

Example 2

Input
root = [9, 6, null, 4, null, 1]
Output
[4, 1, 6, null, null, null, 9]
Why
A left-leaning chain of four values. Rooting at 4 leaves 1 on the left and 6, 9 on the right; [6, 4, 9, 1] would be just as valid.

Example 3

Input
root = [5, 3, 8]
Output
[5, 3, 8]
Why
The tree is already balanced, so returning it as it is works.

Constraints

  • The tree has 1 to 10^4 nodes.
  • 1 <= Node.val <= 10^5
  • The input is a valid binary search tree with distinct values.
  • Any height-balanced BST with exactly the same values is accepted.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Sorted values + new treeO(n)O(n)
Optimal (in-order nodes + relink)O(n)O(n)

1Sorted values + new tree

TimeO(n)Each node is visited once by the traversal and created once by the build.
SpaceO(n)The value list, the traversal stack and n new nodes; the build recursion is only O(log n) deep.

Read the values in sorted order with an in-order traversal (done iteratively, because the input can be a long chain). Then build a fresh tree: the middle value becomes the root, the left half builds the left subtree and the right half the right subtree. Splitting in the middle keeps both sides within one node of each other at every level.

  1. Iterative in-order traversal with a stack; append each value to a list.
  2. build(lo, hi): if lo > hi return null; mid = (lo + hi) / 2; create a node for vals[mid] and build its children from [lo, mid - 1] and [mid + 1, hi].
  3. Return build(0, n - 1).
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            cur = st.pop();
            vals.add(cur.val);
            cur = cur.right;
        }
        return build(vals, 0, vals.size() - 1);
    }

    private TreeNode build(List<Integer> vals, int lo, int hi) {
        if (lo > hi) return null;
        int mid = (lo + hi) >>> 1;
        TreeNode node = new TreeNode(vals.get(mid));
        node.left = build(vals, lo, mid - 1);
        node.right = build(vals, mid + 1, hi);
        return node;
    }
}

Edge cases to test

  • A single node
  • A tree that is already balanced
  • A completely skewed tree (a linked list leaning left or right): avoid deep recursion over it
  • Node counts that are one less than, equal to or one more than a power of two

Hints

Hint 1

An in-order traversal of a BST gives its values in sorted order.

Hint 2

From a sorted list, picking the middle element as the root and recursing on both halves always gives a height-balanced tree.

Hint 3

You do not need new nodes: collect the existing nodes in order and just rewire their left and right pointers.

FAQ

What is the best time complexity for Balance a Binary Search Tree?

Optimal (in-order nodes + relink) runs in O(n) time and O(n) extra space. One traversal and one relinking pass.

Which pattern does Balance a Binary Search Tree use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Balance a Binary Search Tree?

Yes. Sorted values + new tree takes O(n) time and O(n) space. Read the values in sorted order with an in-order traversal (done iteratively, because the input can be a long chain).

Which edge cases should I test for Balance a Binary Search Tree?

A single node; A tree that is already balanced; A completely skewed tree (a linked list leaning left or right): avoid deep recursion over it; Node counts that are one less than, equal to or one more than a power of two.