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

2. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

3. Consider the following buggy code for inserting a value into a BST. Which line contains the subtle bug that causes the insertion to fail silently in some cases?

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

medium

A. Line 2: if root is None

B. Line 4: if val < root.val

C. Line 7: insertIntoBST(root.right, val)

D. Line 5: insertIntoBST(root.left, val)

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to insertIntoBST on root.left or root.right do not update the parent's child pointer.

2. Step 2: Identify missing assignment

   Lines 5 and 7 call insertIntoBST but do not assign the returned subtree back to root.left or root.right, so insertion is lost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing assignment causes silent insertion failure [OK]

Hint: Recursive insert must assign returned subtree to parent's child [OK]

Common Mistakes:

• Not updating parent's child pointer
• Confusing base case with recursive step
• Incorrect comparison operator

4. The following code attempts to recover a BST with two swapped nodes using Morris traversal. Identify the line containing the subtle bug that causes incorrect recovery when the swapped nodes are adjacent in inorder traversal.

def recoverTree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                if not first:
                    first = prev
                    second = current
                else:
                    second = current
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val

medium

A. Swapping values at the end without checking if both nodes are found

B. Line setting second = current inside the first if condition

C. Line setting first = prev inside the second if condition

D. Line setting first = prev inside the first if condition

Solution

1. Step 1: Analyze detection of swapped nodes

   The code sets first and second whenever a violation is found, but overwrites them without preserving the first violation's first node.

2. Step 2: Identify the bug in swapping

   The swap at the end assumes both first and second are found, but if only one violation is detected (adjacent nodes swapped), second may be incorrect or null, causing wrong swap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping without confirming both nodes leads to incorrect recovery in adjacent swaps [OK]

Hint: Must confirm both nodes before swapping values [OK]

Common Mistakes:

• Overwriting first and second on multiple violations
• Swapping values prematurely after first violation
• Not restoring tree structure after Morris traversal

5. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early