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 need to add a new value into a binary tree such that the tree maintains the property where for every node, all values in the left subtree are smaller and all values in the right subtree are larger. Which approach guarantees this insertion is done correctly and efficiently?

easy

A. Use a breadth-first traversal to find the first empty spot and insert the new value there.

B. Perform an inorder traversal to find the correct position and then insert the new node.

C. Traverse the tree from the root, moving left or right based on comparisons, and insert the new node at the correct leaf position.

D. Use a heap insertion algorithm to maintain the tree structure.

Solution

1. Step 1: Understand BST property

   The tree must maintain that left children are smaller and right children are larger than the node.

2. Step 2: Identify insertion method

   Traversing from root and choosing left or right child based on comparison ensures the new value is inserted at the correct leaf position without violating BST properties.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion follows BST ordering rules [OK]

Hint: BST insertion follows value comparisons down the tree [OK]

Common Mistakes:

• Using BFS ignores BST ordering
• Inorder traversal is for traversal, not insertion
• Heap insertion is unrelated to BST

2. Consider the following Python code implementing the Morris inorder traversal to recover a BST with two swapped nodes. Given the input tree with nodes [3,1,4,null,null,2] where nodes 2 and 3 are swapped, what is the value of the variable second.val after the traversal completes?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace inorder traversal with Morris method

   The inorder traversal visits nodes in order: 1, 3, 2, 4. The violations are detected when prev.val > current.val: first at (3,2).

2. Step 2: Identify swapped nodes

   First violation sets first=3, second=2. No second violation occurs, so second remains 2.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Second node detected is the node with value 2 [OK]

Hint: Second swapped node is the smaller value in violation [OK]

Common Mistakes:

• Confusing first and second nodes
• Missing second violation for adjacent swaps
• Off-by-one in traversal order

3. Consider the following code snippet for searching a value in a BST. What will be printed when searching for the value 3 in the given tree?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 3)
print(result.val if result else 'null')

easy

A. 2

B. 7

C. null

D. 3

Solution

1. Step 1: Trace the search path

   Start at root (4). Since 3 < 4, move to left child (2). Since 3 > 2, move to right child (3).

2. Step 2: Check node value

   Current node value is 3, which matches the search value, so return this node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Search follows BST property correctly and finds node with value 3 [OK]

Hint: Follow BST property to move left or right [OK]

Common Mistakes:

• Returning wrong node value due to off-by-one traversal

4. What is the time complexity of the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

Hint: Time depends on tree height, not total nodes [OK]

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here

5. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely