#1382

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Balance a Binary Search Tree

This problem requires balancing a binary search tree using in-order traversal and state tracking techniques.

divide and conquer greedy tree depth first search binary search tree

Problem Statement

Given the root of a binary search tree, your task is to return a balanced binary search tree using the same node values. A balanced binary search tree has subtrees whose depths do not differ by more than one. If there are multiple correct answers, any valid solution will be accepted.

The problem requires converting the binary search tree into a sorted array by performing an in-order traversal. Once sorted, the tree should be reconstructed by selecting the middle node as the root and recursively balancing the left and right subtrees.

Examples

Example 1

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

Output: [2,1,3,null,null,null,4]

This is not the only correct answer, [3,1,4,null,2] is also correct.

Example 2

Input: root = [2,1,3]

Output: [2,1,3]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 105

Solution Approach

In-order Traversal

The first step is to traverse the tree in an in-order fashion, which gives us a sorted array of all the node values. This ensures that we can easily access the middle element to serve as the root for each subtree.

Recursive Tree Reconstruction

Once we have the sorted array, we recursively pick the middle element as the root and build the left and right subtrees using the same logic. This guarantees that the resulting tree is balanced.

Optimizing Space Complexity

To optimize space complexity, consider using a tree traversal that does not require additional arrays, or implement the in-order traversal iteratively. This can reduce the space complexity from O(n) to O(log n) for stack usage.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because we perform an in-order traversal of the tree and rebuild the tree recursively, both of which require processing every node once. The space complexity is O(n) due to the space required for storing the sorted array and recursive calls in the stack.

What Interviewers Usually Probe

Candidate should demonstrate understanding of binary search tree properties.
Look for an efficient use of recursion in constructing the tree.
Pay attention to the explanation of how to balance the tree using the middle element.

Common Pitfalls or Variants

Common pitfalls

Not using in-order traversal to get the sorted node values.
Incorrectly choosing the root node (must be the middle of the sorted list).
Failing to handle large trees efficiently, leading to stack overflows or memory issues.

Follow-up variants

How would this approach change if the input was a linked list?
What if the tree is already balanced? Can we optimize the process?
What if we need to maintain the original structure of the tree instead of balancing it?

FAQ

What is the main pattern in the 'Balance a Binary Search Tree' problem?

The key pattern is binary-tree traversal combined with state tracking. In this problem, the tree is traversed in-order to create a sorted array, and then the tree is reconstructed in a balanced way by selecting the middle element.

How do I balance a binary search tree efficiently?

The efficient way is by performing an in-order traversal to collect node values in a sorted array, then recursively constructing the tree by selecting the middle element of the array as the root.

Can multiple answers exist for this problem?

Yes, there can be multiple valid solutions as long as the tree is balanced. The exact structure may vary, but the general tree properties should remain the same.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of nodes in the tree, because each node is visited once during the in-order traversal and the tree reconstruction.

Why is space complexity O(n)?

Space complexity is O(n) due to the space needed for the sorted array (storing node values) and the recursive stack used during tree reconstruction.

terminal

Solution

Solution 1: In-order Traversal + Construct Balanced Binary Search Tree

Since the original tree is a binary search tree, we can save the result of the in-order traversal in an array $nums$. Then we design a function $build(i, j)$, which is used to construct a balanced binary search tree within the index range $[i, j]$ in $nums$. The answer is $build(0, |nums| - 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode):
            if root is None:
                return
            dfs(root.left)
            nums.append(root.val)
            dfs(root.right)

        def build(i: int, j: int) -> TreeNode:
            if i > j:
                return None
            mid = (i + j) >> 1
            left = build(i, mid - 1)
            right = build(mid + 1, j)
            return TreeNode(nums[mid], left, right)

        nums = []
        dfs(root)
        return build(0, len(nums) - 1)

Continue Practicing

#1373 maximum sum bst in binary tree #1305 all elements in two binary search trees #1569 number of ways to reorder array to get same bst