Interview Prepbinary-search-treesmediumAmazonGoogle

Balance a BST

Choose your preparation mode3 modes available

Try It Solution Trace

📋

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]:

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
}

0/9

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

t1_01basic

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

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

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.

t1_02basic

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

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

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