What happens if you not resetting left and right pointers when rebuilding tree?

Leads to cycles or incorrect tree structure Fix: Explicitly set node.left and node.right to None/null before assigning children

What happens if you using preorder or postorder traversal instead of inorder?

Collected nodes won't be sorted, resulting in invalid BST Fix: Always use inorder traversal to get sorted nodes from BST

What happens if you choosing wrong middle index (e.g., always left or right middle)?

Tree becomes unbalanced or skewed Fix: Use mid = (left + right) // 2 to pick middle element consistently

What happens if you not handling empty tree or single node tree?

Code may crash or return incorrect result Fix: Add base cases to handle empty input and single node properly

Interview Prepbinary-search-treesmediumAmazonGoogle

Balance a BST

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Balance a BST

mediumTREEAmazonGoogle

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.

💡 Balancing a BST means reorganizing nodes so the tree height is minimized, which improves search efficiency. Beginners often struggle because they don't see how to transform an unbalanced tree into a balanced one without losing BST properties. Think of it like rearranging books on a shelf so they are evenly spaced and easy to find.

📋

Problem Statement

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.

💡

Example

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

Output[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.

Single node tree → same tree returned
Already balanced BST → tree remains unchanged
Completely skewed tree (all nodes to one side) → balanced tree with minimal height
Tree with only left children → balanced tree with minimal height

⚠️

Common Mistakes

Not resetting left and right pointers when rebuilding tree

Leads to cycles or incorrect tree structure

✅ Explicitly set node.left and node.right to None/null before assigning children

Using preorder or postorder traversal instead of inorder

Collected nodes won't be sorted, resulting in invalid BST

✅ Always use inorder traversal to get sorted nodes from BST

Choosing wrong middle index (e.g., always left or right middle)

Tree becomes unbalanced or skewed

✅ Use mid = (left + right) // 2 to pick middle element consistently

Not handling empty tree or single node tree

Code may crash or return incorrect result

✅ Add base cases to handle empty input and single node properly

Confusing node values with node references when rebuilding

May create new nodes unnecessarily or lose original node identity

✅ Be clear whether you store values or node references and be consistent

🧠

Brute Force (Inorder Traversal + Rebuild Balanced BST)

💡 This approach is foundational because it breaks down the problem into two simpler steps: flattening the BST into a sorted list and then building a balanced BST from that list. It teaches the importance of inorder traversal and recursive tree construction.

Intuition

Since inorder traversal of a BST yields sorted values, we can collect all nodes in sorted order and then build a balanced BST by recursively choosing the middle element as root.

Algorithm

Perform an inorder traversal of the BST to collect node values in sorted order.
Use the sorted list to recursively build a balanced BST by choosing the middle element as the root.
Recursively build left and right subtrees from the left and right halves of the list.
Return the root of the newly constructed balanced BST.

💡 The challenge is understanding how inorder traversal preserves sorted order and how picking the middle element ensures balance.

</>

Code

from typing import Optional, List

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

def balanceBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
    def inorder(node: Optional[TreeNode], arr: List[int]):
        if not node:
            return
        inorder(node.left, arr)
        arr.append(node.val)
        inorder(node.right, arr)

    def build_balanced_bst(nums: List[int], left: int, right: int) -> Optional[TreeNode]:
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = build_balanced_bst(nums, left, mid - 1)
        root.right = build_balanced_bst(nums, mid + 1, right)
        return root

    sorted_nodes = []
    inorder(root, sorted_nodes)
    return build_balanced_bst(sorted_nodes, 0, len(sorted_nodes) - 1)

# Driver code to test
if __name__ == '__main__':
    # Construct skewed BST: 1 -> 2 -> 3 -> 4
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)
    root.right.right.right = TreeNode(4)

    balanced_root = balanceBST(root)
    # Expected balanced root val: 2
    print(balanced_root.val)

Line Notes

def inorder(node: Optional[TreeNode], arr: List[int]):Defines helper to collect nodes in sorted order

if not node:Base case to stop recursion at leaf's child

arr.append(node.val)Collect current node's value in sorted order

mid = (left + right) // 2Choose middle element to ensure balanced root

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> sortedNodes = new ArrayList<>();
        inorder(root, sortedNodes);
        return buildBalancedBST(sortedNodes, 0, sortedNodes.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> arr) {
        if (node == null) return;
        inorder(node.left, arr);
        arr.add(node.val);
        inorder(node.right, arr);
    }

    private TreeNode buildBalancedBST(List<Integer> nums, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums.get(mid));
        root.left = buildBalancedBST(nums, left, mid - 1);
        root.right = buildBalancedBST(nums, mid + 1, right);
        return root;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);

        TreeNode balancedRoot = sol.balanceBST(root);
        System.out.println(balancedRoot.val); // Expected 2
    }
}

Line Notes

public TreeNode balanceBST(TreeNode root) {Entry point to balance BST

inorder(root, sortedNodes);Collect nodes in sorted order via inorder traversal

int mid = left + (right - left) / 2;Calculate middle index to pick balanced root

root.left = buildBalancedBST(nums, left, mid - 1);Recursively build left subtree

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> sortedNodes;
        inorder(root, sortedNodes);
        return buildBalancedBST(sortedNodes, 0, sortedNodes.size() - 1);
    }

private:
    void inorder(TreeNode* node, vector<int>& arr) {
        if (!node) return;
        inorder(node->left, arr);
        arr.push_back(node->val);
        inorder(node->right, arr);
    }

    TreeNode* buildBalancedBST(const vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildBalancedBST(nums, left, mid - 1);
        root->right = buildBalancedBST(nums, mid + 1, right);
        return root;
    }
};

// Driver code
int main() {
    Solution sol;
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->right = new TreeNode(3);
    root->right->right->right = new TreeNode(4);

    TreeNode* balancedRoot = sol.balanceBST(root);
    cout << balancedRoot->val << endl; // Expected 2
    return 0;
}

Line Notes

void inorder(TreeNode* node, vector<int>& arr) {Helper to collect nodes in sorted order

if (!node) return;Base case to stop recursion

int mid = left + (right - left) / 2;Middle index ensures balanced root selection

root->left = buildBalancedBST(nums, left, mid - 1);Build left subtree recursively

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function balanceBST(root) {
    const sortedNodes = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        sortedNodes.push(node.val);
        inorder(node.right);
    }

    function buildBalancedBST(nums, left, right) {
        if (left > right) return null;
        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = buildBalancedBST(nums, left, mid - 1);
        root.right = buildBalancedBST(nums, mid + 1, right);
        return root;
    }

    inorder(root);
    return buildBalancedBST(sortedNodes, 0, sortedNodes.length - 1);
}

// Driver code
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.right = new TreeNode(3);
root.right.right.right = new TreeNode(4);

const balancedRoot = balanceBST(root);
console.log(balancedRoot.val); // Expected 2

Line Notes

function inorder(node) {Helper to traverse tree inorder and collect values

if (!node) return;Stops recursion at leaf's child

const mid = Math.floor((left + right) / 2);Middle index picks balanced root

root.left = buildBalancedBST(nums, left, mid - 1);Recursively build left subtree

⏱

Complexity

TimeO(n)

SpaceO(n)

Inorder traversal visits all nodes once (O(n)). Building balanced BST from sorted array also takes O(n). Space is O(n) for storing node values.

💡 For n=20 nodes, about 20 operations to traverse and 20 to build, totaling roughly 40 operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and accepted in interviews; it clearly shows understanding of BST properties and recursion.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Inorder + Build Balanced BST with values)	`O(n)`	`O(n)`	No (inorder and build recursion depth O(log n))	Yes	Most common approach to code
2. Inorder + Build Balanced BST with node references	`O(n)`	`O(n)`	No	Yes, reuses nodes	Mention as optimization, code if asked
3. Iterative Balanced BST Construction	`O(n)`	`O(n)`	No	Yes	Rarely code, mention if recursion depth is concern

Practice

(1/5)

1. You are given a binary search tree and a target integer k. You need to determine if there exist two distinct nodes in the BST whose values sum up to k. Which of the following approaches guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to get a sorted array, then use two pointers to find if a pair sums to k.

B. Use dynamic programming to store sums of all subtree pairs and check for k.

C. Perform a brute force nested traversal of all node pairs directly on the BST without extra storage.

D. Use a greedy approach by always choosing the smallest and largest node values and adjusting pointers.

2. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand BST property and inorder traversal

Step 2: Apply two-pointer technique on sorted array

Final Answer:

Quick Check:

Solution

Step 1: Identify thread restoration step

Step 2: Locate missing restoration

Final Answer:

Quick Check:

Solution

Step 1: Identify traversal path length

Step 2: Understand h vs n

Final Answer:

Quick Check:

Solution

Step 1: Understand BST height and search path

Step 2: Analyze worst-case time complexity

Final Answer:

Quick Check:

Solution

Step 1: Check root adjustment logic

Step 2: Verify other lines

Final Answer:

Quick Check:

Ready to prove it?