Convert Sorted Array to Height-Balanced BST

▶

Steps

setup

Initialize and start recursion

Initialize index to 0 and start helper recursion with full array range (0 to 4).

💡 Index tracks nodes created; starting with full range means building entire tree.

Line:

self.index = 0
return self.helper(nums, 0, len(nums) - 1)

💡 The entire array is considered initially to build the root and subtrees.

fill_row

Calculate mid index for root

Calculate mid = (0 + 4) // 2 = 2 to select 0 as root value.

💡 Choosing middle element ensures balanced BST height.

Line:

mid = (left + right) // 2

💡 Midpoint divides array into balanced halves for left and right subtrees.

traverse

Recurse left subtree of root

Call helper recursively for left subtree with range left=0 to right=1.

💡 Left subtree built before root node to maintain structure.

Line:

left_child = self.helper(nums, left, mid - 1)

💡 Recursion breaks problem into smaller subproblems for left subtree.

fill_row

Calculate mid index for left subtree root

Calculate mid = (0 + 1) // 2 = 0 to select -10 as left subtree root.

💡 Midpoint balances left subtree similarly.

Line:

mid = (left + right) // 2

💡 Midpoint divides left subtree array segment.

traverse

Recurse left subtree of -10

Call helper recursively for left subtree of -10 with range left=0 to right=-1, invalid range returns None.

💡 Base case stops recursion when left > right.

Line:

if left > right:
    return None

💡 Base case returns leaf node's child as None.

insert

Create node -10

Create TreeNode with value -10; increment index to 1.

💡 Node creation links recursive calls to tree nodes.

Line:

root = TreeNode(nums[mid])
self.index += 1

💡 Node -10 is now part of BST; index tracks nodes created.

traverse

Recurse right subtree of -10

Call helper recursively for right subtree of -10 with range left=1 to right=1.

💡 Right subtree built before returning node -10.

Line:

root.right = self.helper(nums, mid + 1, right)

💡 Recursion continues building right child of -10.

fill_row

Calculate mid index for right child of -10

Calculate mid = (1 + 1) // 2 = 1 to select -3 as right child of -10.

💡 Midpoint balances this subtree node.

Line:

mid = (left + right) // 2

💡 Midpoint divides this segment to create leaf node.

traverse

Recurse left subtree of -3

Call helper recursively for left subtree of -3 with range left=1 to right=0, invalid range returns None.

💡 Base case reached, no left child for -3.

Line:

if left > right:
    return None

💡 Leaf node's left child is None.

insert

Create node -3

Create TreeNode with value -3; increment index to 2.

💡 Node creation completes this subtree leaf.

Line:

root = TreeNode(nums[mid])
self.index += 1

💡 Node -3 linked as right child of -10.

return

Return left subtree root (-10)

Return node -10 with left child None and right child -3 to previous call (root creation).

💡 Returning subtree root links it to main root's left child.

Line:

return root

💡 Left subtree fully constructed and ready to attach.

insert

Create root node 0

Create TreeNode with value 0 as root; increment index to 3; attach left subtree (-10).

💡 Root node creation connects left subtree and prepares for right subtree.

Line:

root = TreeNode(nums[mid])
self.index += 1
root.left = left_child

💡 Root node 0 is central to balanced BST.

traverse

Recurse right subtree of root

Call helper recursively for right subtree with range left=3 to right=4.

💡 Right subtree must be built to complete BST.

Line:

root.right = self.helper(nums, mid + 1, right)

💡 Right subtree construction begins with smaller array segment.

fill_row

Calculate mid index for right subtree root

Calculate mid = (3 + 4) // 2 = 3 to select 5 as right subtree root.

💡 Midpoint balances right subtree.

Line:

mid = (left + right) // 2

💡 Midpoint divides right subtree array segment.

traverse

Recurse left subtree of 5

Call helper recursively for left subtree of 5 with range left=3 to right=2, invalid range returns None.

💡 Base case reached, no left child for 5.

Line:

if left > right:
    return None

💡 Leaf node's left child is None.

insert

Create node 5

Create TreeNode with value 5; increment index to 4.

💡 Node creation adds right subtree root.

Line:

root = TreeNode(nums[mid])
self.index += 1

💡 Node 5 is now part of BST.

traverse

Recurse right subtree of 5

Call helper recursively for right subtree of 5 with range left=4 to right=4.

💡 Right child of 5 must be built to complete subtree.

Line:

root.right = self.helper(nums, mid + 1, right)

💡 Recursion continues to build right child of 5.

fill_row

Calculate mid index for right child of 5

Calculate mid = (4 + 4) // 2 = 4 to select 9 as right child of 5.

💡 Midpoint creates leaf node 9.

Line:

mid = (left + right) // 2

💡 Midpoint divides last segment to create leaf node.

traverse

Recurse left subtree of 9

Call helper recursively for left subtree of 9 with range left=4 to right=3, invalid range returns None.

💡 Base case reached, no left child for 9.

Line:

if left > right:
    return None

💡 Leaf node's left child is None.

insert

Create node 9 and complete BST

Create TreeNode with value 9; increment index to 5; return node 9, then node 5, then node 0 as root.

💡 Final node creation completes BST; recursion unwinds returning full tree.

Line:

root = TreeNode(nums[mid])
self.index += 1
return root

💡 BST fully constructed with balanced height.

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

class Solution:
    def __init__(self):
        self.index = 0

    def helper(self, nums, left, right):
        # STEP 1-20: Recursive helper to build BST
        if left > right:
            return None  # STEP 5,9,15,19 base case
        mid = (left + right) // 2  # STEP 2,4,8,14,18 mid calculation
        left_child = self.helper(nums, left, mid - 1)  # STEP 3,5,7,9,15,19 recurse left
        root = TreeNode(nums[mid])  # STEP 6,10,12,16,20 create node
        self.index += 1  # STEP 6,10,12,16,20 increment index
        root.left = left_child  # STEP 12 attach left
        root.right = self.helper(nums, mid + 1, right)  # STEP 7,13,17 recurse right
        return root  # STEP 11,20 return node

    def sorted_array_to_bst(self, nums):
        self.index = 0  # STEP 1 initialize
        return self.helper(nums, 0, len(nums) - 1)  # STEP 1 start recursion

if __name__ == '__main__':
    nums = [-10, -3, 0, 5, 9]
    sol = Solution()
    root = sol.sorted_array_to_bst(nums)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

📊

Convert Sorted Array to Height-Balanced BST - Watch the Algorithm Execute, Step by Step

Watching each recursive call and node creation helps you understand how the algorithm balances the tree by choosing midpoints and how recursion unwinds to assemble the final BST.

DFS Stack

null (entered)left=0 right=4 mid=null

DFS Stack

null (entered)left=0 right=4 mid=2

DFS Stack

null (entered)left=0 right=1 mid=nullnull (entered)left=0 right=4 mid=2

DFS Stack

null (entered)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

DFS Stack

null (entered)left=0 right=-1 mid=nullnull (entered)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

Current node: 1

-10

DFS Stack

1 (left_done)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

-10

DFS Stack

null (entered)left=1 right=1 mid=null1 (left_done)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

-10

DFS Stack

null (entered)left=1 right=1 mid=11 (left_done)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

-10

DFS Stack

null (entered)left=1 right=0 mid=nullnull (entered)left=1 right=1 mid=11 (left_done)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

Current node: 2

-10-3

DFS Stack

1 (right_done)left=0 right=1 mid=0null (entered)left=0 right=4 mid=2

Current node: 3

-10-3

DFS Stack

null (left_done)left=0 right=4 mid=2

Return: 1

Current node: 3

-10-30

DFS Stack

3 (left_done)left=0 right=4 mid=2

-10-30

DFS Stack

null (entered)left=3 right=4 mid=null3 (left_done)left=0 right=4 mid=2

-10-30

DFS Stack

null (entered)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

-10-30

DFS Stack

null (entered)left=3 right=2 mid=nullnull (entered)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

Current node: 4

-10-305

DFS Stack

4 (left_done)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

-10-305

DFS Stack

null (entered)left=4 right=4 mid=null4 (left_done)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

-10-305

DFS Stack

null (entered)left=4 right=4 mid=44 (left_done)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

-10-305

DFS Stack

null (entered)left=4 right=3 mid=nullnull (entered)left=4 right=4 mid=44 (left_done)left=3 right=4 mid=33 (left_done)left=0 right=4 mid=2

Current node: 3

-10-3059

Return: 3

Key Takeaways

✓ Choosing the middle element as root at each recursive step ensures the BST is height-balanced.

This insight is hard to see from code alone but clear when watching the recursive splits and node creations.

✓ The recursion builds left subtree first, then root, then right subtree, which is crucial for correct BST construction.

Understanding the order of recursion helps grasp how the tree nodes are linked properly.

✓ Base cases where left > right stop recursion and return None, marking leaf nodes' children.

Visualizing base cases clarifies when recursion ends and how leaf nodes are formed.

Practice

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

2. What is the time complexity of the iterative inorder traversal approach to find the kth smallest element in a BST, where H is the height of the tree and k is the input parameter?

medium

A. O(H + k), where H is the height of the tree and k is the kth element to find

B. O(k), since only k nodes are visited

C. O(k log n), assuming balanced BST

D. O(n), where n is the total number of nodes in the BST

Solution

1. Step 1: Analyze traversal steps

   The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.

2. Step 2: Combine costs

   Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal cost depends on height plus k nodes visited [OK]

Hint: Traversal cost includes height plus k nodes visited [OK]

Common Mistakes:

• Assuming O(n) always
• Ignoring height cost
• Assuming only k nodes visited without stack overhead

3. What is the worst-case time complexity of the optimal iterative BST search algorithm when searching for a value in a BST with n nodes and height h?

medium

A. O(log n) always because BSTs are balanced.

B. O(n) because you might have to visit every node in the tree.

C. O(h) because the search path follows the height of the tree.

D. O(1) because the search uses direct indexing.

Solution

1. Step 1: Understand BST height and search path

   The search path length is at most the height h of the BST, as each step moves down one level.

2. Step 2: Analyze worst-case time complexity

   In worst case (unbalanced tree), h can be up to n, but complexity is expressed as O(h), not O(n) directly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search complexity depends on tree height, not total nodes necessarily [OK]

Hint: Time depends on tree height, not total nodes always [OK]

Common Mistakes:

• Assuming O(log n) always, ignoring unbalanced trees

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

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