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. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

2. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

3. You are given a binary tree where each node has a unique integer value. You need to find whether a given value exists in the tree efficiently by leveraging the tree's ordering properties. Which approach guarantees the fastest search in the worst case?

easy

A. Use the BST property to decide whether to search left or right subtree at each node, recursively or iteratively.

B. Perform a breadth-first search (BFS) to find the value level by level.

C. Traverse the entire tree recursively checking each node until the value is found.

D. Use dynamic programming to store previously searched subtrees to avoid repeated work.

Solution

1. Step 1: Understand the problem constraints

   The tree is a BST, so left subtree nodes are less than the node, right subtree nodes are greater.

2. Step 2: Identify the optimal search approach

   Using the BST property allows skipping half of the tree at each step, leading to O(h) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BST property guides search direction efficiently [OK]

Hint: BST property enables directed search, not full traversal [OK]

Common Mistakes:

• Thinking BFS or full traversal is optimal for BST search

4. Consider the following buggy code for deleting a node in a BST. Which line contains the subtle bug that can cause the BST property to break when deleting a node with two children?

def deleteNode(root, key):
    if not root:
        return null
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            successor = findSuccessor(root)
            root.val = successor.val
            root.left = deleteNode(root.right, successor.val)  # Bug here
    return root

medium

A. Line where root.left is assigned deleteNode(root.right, successor.val)

B. Line where root.left is assigned deleteNode(root.left, key)

C. Line where root.val is set to successor.val

D. Line where root.right is assigned deleteNode(root.right, key)

Solution

1. Step 1: Identify two-children deletion logic

   When deleting a node with two children, we replace its value with the successor's value and then delete the successor from the right subtree.

2. Step 2: Spot incorrect subtree assignment

   The line assigns root.left = deleteNode(root.right, successor.val), which incorrectly deletes from the right subtree but assigns result to left child, breaking BST structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct line should assign root.right = deleteNode(root.right, successor.val) [OK]

Hint: Deleting successor must update right subtree, not left [OK]

Common Mistakes:

• Mixing left and right subtree assignments
• Forgetting to update parent's child pointer
• Replacing value but not deleting successor

5. Suppose you want to modify the BST insertion algorithm to allow inserting duplicate values by always inserting duplicates into the left subtree. Which of the following changes to the iterative insertion code below correctly implements this behavior without breaking the BST property?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while curr:
        parent = 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

hard

A. Change the condition to if val <= curr.val: and insert duplicates to the left subtree.

B. Change the condition to if val < curr.val: and insert duplicates to the right subtree.

C. Always insert duplicates as new root nodes to maintain BST property.

D. Disallow duplicates by returning the original tree without insertion.

Solution

1. Step 1: Understand duplicate insertion rule

   Duplicates must go to the left subtree, so values equal to current node should be treated as less or equal.

2. Step 2: Modify comparison operator

   Changing condition to val <= curr.val ensures duplicates follow left subtree insertion path, preserving BST property.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates inserted left by using <= comparison [OK]

Hint: Use <= to direct duplicates left, preserving BST order [OK]

Common Mistakes:

• Inserting duplicates right breaks problem requirement
• Inserting duplicates as new roots breaks BST
• Ignoring duplicates causes infinite recursion