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. 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 Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

3. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

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

5. What is the worst-case time complexity of the optimized iterative DFS with BST pruning approach for computing the range sum of a BST with n nodes and height h?

medium

A. O(h) because only nodes along the height are visited

B. O(log n) because pruning skips most nodes

C. O(n) because in worst case pruning does not skip any nodes

D. O(n log n) because each node may be visited multiple times due to stack operations

Solution

1. Step 1: Identify worst-case scenario

   Worst case occurs when all nodes fall within the range or pruning is ineffective, so all n nodes are visited.

2. Step 2: Analyze time complexity

   Each node is processed once, so time complexity is O(n). Stack operations are O(1) amortized per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Worst case is full traversal, O(n) time [OK]

Hint: Worst case equals full traversal of all nodes [OK]

Common Mistakes:

• Assuming pruning always reduces to O(log n)
• Confusing height h with number of nodes n