Convert Sorted Array to Height-Balanced BST

📋

Problem

Imagine you have a sorted list of book IDs and want to organize them in a way that allows quick search and insertion. Creating a balanced binary search tree from this sorted list ensures efficient operations.

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in ascending order

Edge cases: Single element array → tree with one nodeTwo elements array → root and one childAll elements are the same → balanced tree with duplicates allowed

</>

IDE

def sorted_array_to_bst(nums: list[int]) -> list[int]:public int[] sortedArrayToBST(int[] nums)vector<int> sortedArrayToBST(vector<int>& nums)function sortedArrayToBST(nums)

def sorted_array_to_bst(nums):
    # Write your solution here
    pass

class Solution {
    public int[] sortedArrayToBST(int[] nums) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> sortedArrayToBST(vector<int>& nums) {
    // Write your solution here
    return {};
}

function sortedArrayToBST(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [ -10, null, -3, null, 0, null, 5, null, 9 ]Inserting elements one by one into BST without balancing, resulting in skewed tree.✅ Use recursive divide and conquer approach selecting middle element as root instead of sequential insertion.

Wrong: [ 0, -10, 5, null, -3, null, 9 ]Incorrect mid index calculation causing wrong root selection and unbalanced tree.✅ Calculate mid as (left + right) // 2 to select correct middle element.

Wrong: [ 2, 2, 2, 2, 2 ]Not handling duplicates properly, causing invalid BST or unbalanced tree.✅ Allow duplicates by consistently choosing middle element as root and placing duplicates in left or right subtree.

Wrong: Function crashes or returns non-empty output on empty inputNo base case for empty input array.✅ Add base case: if nums is empty, return empty list.

Wrong: TLE on large inputUsing O(n^2) insertion approach instead of O(n) divide and conquer.✅ Implement recursive divide and conquer approach selecting middle element as root to achieve O(n) time.

✓

Test Cases

Try testing your code with empty and single element arrays to catch base case bugs.

Test with duplicates and check your mid index calculation to avoid off-by-one errors.

Optimize your solution to O(n) by using divide and conquer recursion instead of repeated insertions.

t1_01basic

Input{"nums":[-10,-3,0,5,9]}

Expected[0,-3,9,-10,null,5,null]

⏱ Performance - must finish in 2000ms

Choosing 0 as root splits array into left [-10, -3] and right [5, 9]. Recursively building subtrees results in a balanced BST. Output is level order traversal with nulls for missing nodes.

💡 Think about choosing the middle element as the root to balance the tree.

💡 Use divide and conquer: recursively build left and right subtrees from subarrays.

💡 Return the tree as a level order traversal array including nulls for missing children.

Why it failed: Incorrect tree structure or unbalanced tree. Likely inserting nodes one by one without balancing. Fix by choosing middle element as root recursively.

✓ Correct balanced BST constructed using middle element recursion.

t1_02basic

Input{"nums":[1,2,3,4,5,6,7]}

Expected[4,2,6,1,3,5,7]

⏱ Performance - must finish in 2000ms

Middle element 4 chosen as root, left subtree from [1,2,3], right subtree from [5,6,7]. Balanced BST with level order traversal output.

💡 Pick the middle element as root to keep tree balanced.

💡 Recursively apply the same logic to left and right halves.

💡 Return the tree as a level order traversal array including nulls for missing nodes.

Why it failed: Unbalanced tree or incorrect node placement. Possibly inserting sequentially without middle selection. Fix by recursive middle element selection.

✓ Balanced BST correctly constructed with middle element recursion.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array results in empty tree (empty level order traversal).

💡 Check how your code handles empty input arrays.

💡 Return an empty list or null tree when input is empty.

💡 Add a base case to return empty output if nums is empty.

Why it failed: Function crashes or returns non-empty output on empty input. Fix by adding base case: if nums is empty, return empty list.

✓ Correctly returns empty tree for empty input.

t2_02edge

Input{"nums":[42]}

Expected[42]

⏱ Performance - must finish in 2000ms

Single element array results in a tree with one node only.

💡 For single element, the root is that element itself.

💡 No left or right children should exist.

💡 Return a list with single element representing the root node.

Why it failed: Incorrect output for single element input, possibly empty or extra nodes. Fix by returning single node tree when nums length is 1.

✓ Correctly returns single node tree for single element input.

t2_03edge

Input{"nums":[1,2]}

Expected[2,1]

⏱ Performance - must finish in 2000ms

Two elements: root is middle element 2, left child is 1, no right child, resulting in balanced BST.

💡 With two elements, pick middle as root to keep balance.

💡 One child will be null, the other will be the second element.

💡 Return level order traversal with null for missing right child.

Why it failed: Incorrect tree shape for two elements, e.g. both children or unbalanced. Fix by choosing middle element as root and placing other as child.

✓ Correct balanced BST with two nodes constructed.

t3_01corner

Input{"nums":[2,2,2,2,2]}

Expected[2,2,2,null,2,null,2,null]

⏱ Performance - must finish in 2000ms

All elements identical; balanced BST still possible by choosing middle element each time.

💡 Duplicates do not break BST property if placed consistently.

💡 Choose middle element as root recursively even if values are same.

💡 Return level order traversal with nulls for missing children.

Why it failed: Incorrect handling of duplicates causing unbalanced or invalid BST. Fix by always choosing middle element as root regardless of duplicates.

✓ Balanced BST correctly constructed with duplicates.

t3_02corner

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

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

⏱ Performance - must finish in 2000ms

Greedy approach picking first or last element as root fails balance; correct is middle element 3 as root.

💡 Avoid greedy choice of first or last element as root.

💡 Use divide and conquer picking middle element to ensure balance.

💡 Return level order traversal with nulls for missing children.

Why it failed: Greedy root selection causes skewed tree and fails balance. Fix by selecting middle element as root recursively.

✓ Balanced BST constructed by middle element selection.

t3_03corner

Input{"nums":[1,3,5,7,9,11]}

Expected[5,3,9,1,null,7,11]

⏱ Performance - must finish in 2000ms

Off-by-one errors in mid calculation cause unbalanced tree; correct mid is floor of (left+right)/2.

💡 Check mid index calculation carefully to avoid off-by-one errors.

💡 Use mid = (left + right) // 2 for integer division.

💡 Return level order traversal with nulls for missing children.

Why it failed: Off-by-one mid index causes incorrect root selection and unbalanced tree. Fix by using integer division mid = (left + right) // 2.

✓ Balanced BST constructed with correct mid index calculation.

t4_01performance

Input{"nums":[-10000,-99980,-99960,-99940,-99920,-99900,-99880,-99860,-99840,-99820,-99800,-99780,-99760,-99740,-99720,-99700,-99680,-99660,-99640,-99620,-99600,-99580,-99560,-99540,-99520,-99500,-99480,-99460,-99440,-99420,-99400,-99380,-99360,-99340,-99320,-99300,-99280,-99260,-99240,-99220,-99200,-99180,-99160,-99140,-99120,-99100,-99080,-99060,-99040,-99020,-99000,-98980,-98960,-98940,-98920,-98900,-98880,-98860,-98840,-98820,-98800,-98780,-98760,-98740,-98720,-98700,-98680,-98660,-98640,-98620,-98600,-98580,-98560,-98540,-98520,-98500,-98480,-98460,-98440,-98420,-98400,-98380,-98360,-98340,-98320,-98300,-98280,-98260,-98240,-98220,-98200,-98180,-98160,-98140,-98120,-98100,-98080,-98060,-98040,-98020]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 to test O(n) divide and conquer approach completes within 2 seconds.

💡 Use divide and conquer recursion with O(n) complexity.

💡 Avoid inserting nodes one by one which is O(n^2).

💡 Use mid element selection and recursion to build balanced BST efficiently.

Why it failed: TLE due to O(n^2) insertion approach. Fix by implementing O(n) divide and conquer recursion.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

2. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

3. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while curr:
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

4. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

5. Suppose the BST deletion operation is modified so that duplicate keys are allowed and stored in the right subtree. How should the deletion algorithm be adapted to correctly delete a node with duplicates?

hard

A. Always delete the first occurrence found and ignore duplicates in the right subtree.

B. Replace the node with its in-order predecessor instead of successor to handle duplicates correctly.

C. Modify the successor search to find the leftmost node with the same key in the right subtree before deletion.

D. When deleting a node with duplicates, delete the node and recursively delete all duplicates in the right subtree with the same key.

Solution

1. Step 1: Understand duplicates stored in right subtree

   Duplicates appear as nodes with the same key in the right subtree, so deleting one occurrence requires deleting all duplicates to maintain correctness.

2. Step 2: Adapt deletion to remove all duplicates

   After deleting the target node, recursively delete all nodes in the right subtree with the same key to remove duplicates fully.

3. Step 3: Why other options fail

   Ignoring duplicates leaves them in tree (A), replacing with predecessor doesn't address duplicates (B), and modifying successor search (D) doesn't remove all duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Deleting all duplicates ensures BST correctness with duplicates allowed [OK]

Hint: Duplicates require recursive deletion of all matching keys [OK]

Common Mistakes:

• Deleting only one node leaves duplicates
• Using predecessor doesn't solve duplicates
• Modifying successor search misses duplicates