Balance a BST

📋

Problem

Imagine you have a binary search tree that has become skewed after many insertions and deletions, causing inefficient operations. Your task is to rebalance it to restore optimal search times.

Given the root of a binary search tree (BST), return a balanced BST with the same node values. A balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique integers.The input tree is a valid BST.

Edge cases: Single node tree → same tree returnedAlready balanced BST → tree remains unchangedCompletely skewed tree (all nodes to one side) → balanced tree with minimal height

</>

IDE

def balanceBST(root: Optional[TreeNode]) -> Optional[TreeNode]:public TreeNode balanceBST(TreeNode root)TreeNode* balanceBST(TreeNode* root)function balanceBST(root)

def balanceBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
    # Write your solution here
    pass

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* balanceBST(TreeNode* root) {
    // Write your solution here
    return nullptr;
}

function balanceBST(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Skewed tree output identical to inputDid not perform balancing; returned input tree as is.✅ Perform inorder traversal and rebuild balanced BST from sorted values.

Wrong: Balanced tree missing some nodes or duplicated nodesOff-by-one errors in recursive build causing incorrect subtree ranges.✅ Correctly handle left and right indices in recursive calls to include all nodes exactly once.

Wrong: Output tree structure differs for already balanced inputAlways rebuilding tree without preserving balanced structure.✅ Ensure rebuilding balanced BST produces identical structure for balanced inputs.

Wrong: Timeout on large inputUsing exponential or quadratic time approach instead of O(n).✅ Use inorder traversal and balanced BST construction in O(n) time.

✓

Test Cases

Focus on handling base cases and boundary conditions carefully.

Watch out for common algorithmic pitfalls like greedy choices and off-by-one errors.

Optimize your solution to run in linear time for large inputs.

t1_01basic

Input{"root":[1,null,2,null,3,null,4,null,null]}

Expected[2,1,3,null,null,null,4]

⏱ Performance - must finish in 2000ms

The input BST is skewed to the right. After balancing, the tree root becomes 2 with left child 1 and right subtree rooted at 3 with right child 4.

💡 Try inorder traversal to get sorted node values.

💡 Use the sorted values to build a balanced BST by choosing middle elements as roots.

💡 Recursively build left and right subtrees from the halves of the sorted array.

Why it failed: Failed to balance skewed tree correctly. Possibly did not use inorder traversal or did not pick middle element as root. Fix by performing inorder traversal and building balanced BST from middle element.

✓ Correctly balanced the skewed BST using inorder traversal and balanced BST construction.

t1_02basic

Input{"root":[3,1,4,null,2]}

Expected[3,1,4,null,2]

⏱ Performance - must finish in 2000ms

The input BST is already balanced, so the output remains the same.

💡 Check if the tree is already balanced by comparing subtree heights.

💡 If balanced, the output should be identical to input.

💡 Ensure your algorithm does not unnecessarily change balanced trees.

Why it failed: Output differs from input for already balanced BST. Possibly rebuilding tree without checking balance or always reconstructing. Fix by ensuring balanced trees remain unchanged or rebuilt identically.

✓ Correctly identified and preserved already balanced BST.

t2_01edge

Input{"root":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single node tree remains unchanged after balancing.

💡 A single node tree is trivially balanced.

💡 Inorder traversal returns one element; rebuilding returns the same node.

💡 Ensure your code handles single node without errors.

Why it failed: Failed on single node tree. Possibly mishandled base case or returned null. Fix by returning the node itself when only one node exists.

✓ Correctly handled single node tree.

t2_02edge

Input{"root":[5,4,null,3,null,2,null,1]}

Expected[3,2,5,1,null,4,null,null,null,null,null]

⏱ Performance - must finish in 2000ms

Input is a left-skewed tree; output is balanced with minimal height.

💡 Left skewed trees have all nodes in left subtree.

💡 Inorder traversal yields sorted ascending values.

💡 Build balanced BST by choosing middle element as root recursively.

Why it failed: Failed to balance left skewed tree. Possibly only handled right skew or did not pick middle element correctly. Fix by always choosing middle element of inorder list as root.

✓ Correctly balanced left skewed tree.

t2_03edge

Input{"root":[2,1,3]}

Expected[2,1,3]

⏱ Performance - must finish in 2000ms

Input is already balanced with 3 nodes; output remains unchanged.

💡 Small balanced trees should remain unchanged.

💡 Inorder traversal returns sorted array; rebuilding yields same structure.

💡 Check that your code does not alter balanced trees unnecessarily.

Why it failed: Output differs from input for small balanced tree. Possibly rebuilding incorrectly or changing structure. Fix by ensuring balanced trees are rebuilt identically.

✓ Correctly preserved small balanced tree.

t3_01corner

Input{"root":[1,null,2,null,3,null,4,null,5]}

Expected[3,2,5,1,null,4,null,null,null]

⏱ Performance - must finish in 2000ms

Right skewed tree with 5 nodes balanced to minimal height tree.

💡 Greedy approach picking first or last element as root fails here.

💡 Use middle element of inorder traversal to avoid skew.

💡 Build balanced BST recursively from sorted node values.

Why it failed: Greedy root selection (always first or last) leads to skewed tree. Fix by selecting middle element of inorder traversal as root.

✓ Correctly avoided greedy trap by choosing middle element as root.

t3_02corner

Input{"root":[10,5,15,2,7,null,20,1]}

Expected[7,2,15,1,5,null,20,null,null]

⏱ Performance - must finish in 2000ms

Unbalanced BST with mixed left and right skew balanced correctly.

💡 Ensure inorder traversal collects all nodes in sorted order.

💡 Avoid off-by-one errors in recursive build indices.

💡 Use inclusive left and right indices correctly when building BST.

Why it failed: Off-by-one error in recursive build causes missing or duplicated nodes. Fix by correctly handling left and right indices in recursion.

✓ Correctly handled recursion boundaries to build balanced BST.

t3_03corner

Input{"root":[8,3,10,1,6,null,14,null,null,4,7,13]}

Expected[7,3,13,1,4,10,14,null,6,null,null,null,null]

⏱ Performance - must finish in 2000ms

Complex BST balanced correctly, testing correct subtree construction.

💡 Check that left and right subtree constructions use correct subarrays.

💡 Verify that node values are unique and used exactly once.

💡 Ensure no node is lost or duplicated during reconstruction.

Why it failed: Nodes lost or duplicated due to incorrect subarray slicing. Fix by carefully slicing inorder array for left and right subtrees.

✓ Correctly reconstructed balanced BST with all nodes.

t4_01performance

Input{"root":[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Input is a right skewed BST with 100 nodes. The solution must run in O(n) time to balance within 2 seconds.

💡 Inorder traversal and balanced BST construction runs in O(n) time.

💡 Avoid recursive calls that cause exponential time.

💡 Use efficient array slicing or indices to build balanced BST.

Why it failed: Solution timed out due to exponential or higher complexity. Fix by implementing O(n) inorder traversal and balanced BST construction.

✓ Solution runs in O(n) time and balances large BST efficiently.

Practice

1. You are given a binary search tree and a key. You need to remove the node with this key while maintaining the BST property. Which approach guarantees the correct and efficient deletion in all cases, including nodes with two children?

easy

A. Use a greedy approach that always deletes the node by replacing it with its left child, ignoring the right subtree.

B. Perform a breadth-first traversal to find and remove the node, then rebuild the tree from scratch.

C. Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor.

D. Use dynamic programming to store subtrees and delete nodes based on precomputed results.

Solution

1. Step 1: Understand BST deletion cases

   Deletion must handle three cases: leaf node, node with one child, and node with two children. The two children case requires replacing the node with its in-order successor or predecessor to maintain BST properties.

2. Step 2: Identify approach that handles all cases correctly

   The recursive approach that finds the node, replaces it with its in-order successor if it has two children, and recursively deletes the successor ensures correctness and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor. correctly handles all deletion cases preserving BST [OK]

Hint: Two-children deletion requires successor replacement [OK]

Common Mistakes:

• Greedy deletion ignoring right subtree breaks BST
• Rebuilding tree is inefficient
• Dynamic programming irrelevant here

2. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

4. Consider the following buggy code snippet for finding the kth smallest element in a BST. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Bug introduced: k is used as zero-based index (count == k-1) instead of one-based

medium

A. Line with 'if count == k - 1:'

B. Line with 'count += 1'

C. Line with 'stack.append(current)'

D. Line with 'current = current.right'

Solution

1. Step 1: Identify the off-by-one bug

   The condition uses 'count == k - 1' which treats k as zero-based, but k is one-based in problem definition.

2. Step 2: Consequence of bug

   This causes the function to return the (k-1)th smallest element or miss the kth element, leading to incorrect results or runtime errors if k=1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct condition must be 'count == k' to match one-based indexing [OK]

Hint: Check indexing base for k carefully [OK]

Common Mistakes:

• Using zero-based index for k
• Misplacing count increment
• Returning too early

5. Consider the following buggy code for trimming a BST. Which line contains the subtle bug that can cause the resulting tree to violate BST properties or cause runtime errors?

medium

A. Line 3: root = root.left when root.val < low

B. Line 5: root = root.left when root.val > high

C. Line 10: cur.left = cur.left.right inside left subtree trimming

D. Line 16: cur.right = cur.right.left inside right subtree trimming

Solution

1. Step 1: Check root adjustment logic

   If root.val < low, root should move to root.right, not root.left, to find valid nodes.

2. Step 2: Verify other lines

   Line 5 correctly moves root to root.left if root.val > high. Lines 10 and 16 correctly adjust subtree pointers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer move causes invalid pruning or infinite loop [OK]

Hint: Root moves wrong direction when value < low [OK]

Common Mistakes:

• Confusing left and right subtree moves
• Incorrect pointer updates causing invalid BST