How do you solve Balance a Binary Search Tree on LeetCode?

Balance a Binary Search Tree (LeetCode #1382) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: In-order traversal is key to obtaining sorted values from a BST.

What is the brute force solution for Balance a Binary Search Tree?

The brute force approach for Balance a Binary Search Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves converting the binary search tree (BST) into a sorted array using in-order traversal and then constructing a balanced BST from that array. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Balance a Binary Search Tree?

Explain your thought process clearly while coding. Discuss the time and space complexity of your approach. Be prepared to discuss alternative methods and their trade-offs.

What are common mistakes when solving Balance a Binary Search Tree?

Not performing in-order traversal correctly. Failing to handle edge cases like single-node trees.

#1382

Balance a Binary Search Tree

Medium

Divide and ConquerGreedyTreeDepth-First SearchBinary Search TreeBinary TreeDivide and ConquerIn-order Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution also involves in-order traversal to get the sorted values, but it constructs the balanced BST in a more efficient manner by using a recursive helper function that directly builds the tree without creating an intermediate array.

⚙️

Algorithm

3 steps

1Step 1: Perform an in-order traversal to count the number of nodes in the BST.
2Step 2: Use a recursive function that constructs the balanced BST by selecting the middle node as the root, using the count to determine the correct node.
3Step 3: Recursively build the left and right subtrees from the remaining nodes.

solution.py37 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def balanceBST(self, root: TreeNode) -> TreeNode:
10        def count_nodes(node):
11            if not node:
12                return 0
13            return 1 + count_nodes(node.left) + count_nodes(node.right)
14
15        def build_balanced_bst(start, end):
16            nonlocal index
17            if start > end:
18                return None
19            mid = (start + end) // 2
20            left = build_balanced_bst(start, mid - 1)
21            root = TreeNode(nodes[index])
22            index += 1
23            root.left = left
24            root.right = build_balanced_bst(mid + 1, end)
25            return root
26
27        nodes = []
28        def in_order(node):
29            if not node:
30                return
31            in_order(node.left)
32            nodes.append(node.val)
33            in_order(node.right)
34
35        in_order(root)
36        index = 0
37        return build_balanced_bst(0, len(nodes) - 1)

ℹ

Complexity note: The in-order traversal takes O(n) time and space to store the node values, and constructing the balanced BST takes O(n) time as well, leading to an overall complexity of O(n).

1In-order traversal is key to obtaining sorted values from a BST.
2Choosing the middle element during construction ensures balance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.