Two Sum IV in BST

▶

Steps

setup

Initialize root and empty array for inorder traversal

We start with the root node of the BST and an empty array to store the inorder traversal result.

💡 Setting up the array is essential to collect node values in sorted order via inorder traversal.

Line:

arr = []

💡 The array will hold the BST values in ascending order after traversal.

traverse

Enter inorder traversal at root (5)

Start inorder traversal by entering the root node 5, preparing to traverse its left subtree first.

💡 Inorder traversal visits left subtree before the node itself, so we first go left.

Line:

inorder(root.left, arr)

💡 Traversal is recursive and depth-first, starting at the leftmost node.

traverse

Traverse left subtree of node 5 to node 3

Move down to the left child node 3 to continue inorder traversal.

💡 We keep going left to reach the smallest values first.

Line:

inorder(root.left, arr)

💡 The traversal stack grows as we go deeper into left children.

traverse

Traverse left subtree of node 3 to node 2

Continue left traversal to node 2, the left child of 3.

💡 Leftmost nodes are visited first in inorder traversal.

Line:

inorder(root.left, arr)

💡 We reach the smallest node in this subtree, ready to append its value.

fill_cells

Append node 2 value to array

Node 2 has no left child, so we append its value 2 to the array.

💡 Appending node values in inorder ensures the array is sorted.

Line:

arr.append(root.val)

💡 The first value in the sorted array is 2, the smallest in the BST.

traverse

Return from node 2 and traverse right subtree (none)

Node 2 has no right child, so we return to node 3 to process it.

💡 After left and node visit, inorder goes to right subtree.

Line:

inorder(root.right, arr)

💡 Traversal backtracks to parent after finishing left subtree.

fill_cells

Append node 3 value to array

After finishing left subtree, append node 3's value to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3], continuing sorted order.

traverse

Traverse right subtree of node 3 to node 4

Move to the right child of node 3, which is node 4, to continue inorder traversal.

💡 After visiting a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 4 value to array

Node 4 has no left child, so append its value 4 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4], continuing sorted order.

fill_cells

Return to node 5 and append its value

After finishing left subtree of 5, append node 5's value to the array.

💡 Node values are appended after left subtree is fully traversed.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5], continuing sorted order.

traverse

Traverse right subtree of node 5 to node 6

Move to the right child of node 5, which is node 6, to continue inorder traversal.

💡 After processing a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 6 value to array (no left child)

Node 6 has no left child, so append its value 6 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5, 6], continuing sorted order.

traverse

Traverse right subtree of node 6 to node 7

Move to the right child of node 6, which is node 7, to continue inorder traversal.

💡 After visiting a node, inorder traversal visits its right subtree.

Line:

inorder(root.right, arr)

💡 Traversal continues to the next higher value node in the BST.

fill_cells

Append node 7 value to array

Node 7 has no left child, so append its value 7 to the array.

💡 Appending node values in inorder ensures sorted order.

Line:

arr.append(root.val)

💡 The array now contains [2, 3, 4, 5, 6, 7], the full sorted list of BST values.

setup

Initialize two pointers for two-sum search

After inorder traversal, initialize left pointer at start (0) and right pointer at end (5) of the sorted array.

💡 Two pointers allow efficient search for two values summing to k.

Line:

left, right = 0, len(arr) - 1

💡 Pointers start at the smallest and largest values in the array.

compare

Check sum of values at pointers (2 + 7)

Calculate sum of values at left (2) and right (7) pointers: 2 + 7 = 9.

💡 Comparing sum to target k determines pointer movement.

Line:

s = arr[left] + arr[right]

💡 Sum equals target, so the pair is found.

from typing import Optional, List

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

def inorder(root: Optional[TreeNode], arr: List[int]) -> None:
    if root is None:
        return
    inorder(root.left, arr)  # STEP: traverse left subtree
    arr.append(root.val)      # STEP: append current node value
    inorder(root.right, arr) # STEP: traverse right subtree

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    arr = []
    inorder(root, arr)        # STEP: get sorted array from BST
    left, right = 0, len(arr) - 1  # STEP: initialize two pointers
    while left < right:
        s = arr[left] + arr[right]  # STEP: compute sum
        if s == k:
            return True             # STEP: found target sum
        elif s < k:
            left += 1              # STEP: move left pointer right
        else:
            right -= 1             # STEP: move right pointer left
    return False                    # STEP: no pair found

📊

Two Sum IV in BST - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the BST structure is leveraged to produce a sorted array and how the two-pointer method efficiently finds the target sum without extra tree traversals.

536247

Current node: 0

536247

DFS Stack

0 (entered)

Current node: 1

536247

DFS Stack

1 (entered)0 (left_done)

Current node: 2

532467

DFS Stack

2 (entered)1 (left_done)0 (left_done)

Current node: 2

532467

DFS Stack

2 (returning)1 (left_done)0 (left_done)

Result: [2]

Current node: 1

532467

DFS Stack

1 (entered)0 (left_done)

Result: [2]

Current node: 1

532467

DFS Stack

1 (returning)0 (left_done)

Result: [2, 3]

Current node: 4

532467

DFS Stack

1 (right_done)0 (left_done)

Result: [2, 3]

Current node: 4

532467

DFS Stack

1 (returning)0 (left_done)

Result: [2, 3, 4]

Current node: 0

532467

DFS Stack

0 (returning)

Result: [2, 3, 4, 5]

Current node: 2

532467

DFS Stack

2 (entered)

Result: [2, 3, 4, 5]

Current node: 2

532467

DFS Stack

2 (returning)

Result: [2, 3, 4, 5, 6]

Current node: 5

532467

DFS Stack

5 (entered)

Result: [2, 3, 4, 5, 6]

Current node: 5

532467

DFS Stack

5 (returning)

Result: [2, 3, 4, 5, 6, 7]

Result: [2, 3, 4, 5, 6, 7]

Result: [2, 3, 4, 5, 6, 7]

Return: true

Key Takeaways

✓ Inorder traversal of a BST produces a sorted array of node values.

This insight is hard to see from code alone because recursion and tree structure hide the order of node visits.

✓ The two-pointer technique efficiently finds two numbers summing to k in a sorted array.

Visualizing pointer movements clarifies why moving left or right pointer depends on the sum comparison.

✓ The algorithm stops immediately when the target sum is found, avoiding unnecessary checks.

Seeing the exact step where sum equals k helps understand early termination in search.

Practice

1. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

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

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

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Solution

1. Step 1: Trace insertion path

   Start at root (4). Since 5 > 4, move right to node 7. Update parent to 4.

2. Step 2: Check right child of 7

   5 < 7, so move left. Left child of 7 is None, so insert here. Parent is now 7, but last parent before insertion was 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Parent is last non-null node before insertion -> 4 [OK]

Hint: Parent tracks last node before insertion point [OK]

Common Mistakes:

• Confusing parent with current node
• Off-by-one in loop iteration
• Mistaking inserted value as parent

2. You are given a binary search tree and asked to find the kth smallest element efficiently without traversing the entire tree. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform a full inorder traversal to collect all elements in a list, then return the kth element from the list.

B. Use an iterative inorder traversal with a stack, stopping as soon as the kth smallest element is found.

C. Apply a greedy approach by always moving to the left child until k steps are taken.

D. Use dynamic programming to store counts of nodes in subtrees and then navigate to the kth element.

Solution

1. Step 1: Understand the problem constraints

   We want to find the kth smallest element in a BST efficiently, avoiding unnecessary traversal.

2. Step 2: Evaluate approaches

   Full inorder traversal (A) is correct but not optimal since it traverses the entire tree. Greedy left moves (C) fail because the kth element may not be in the leftmost path. DP (D) is complex and not standard for this problem. Iterative inorder with early stopping (B) visits only needed nodes, achieving O(H + k) time and O(H) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative inorder with early stopping avoids full traversal [OK]

Hint: Early stopping in inorder traversal is optimal [OK]

Common Mistakes:

• Assuming full traversal is necessary
• Confusing greedy left moves with inorder traversal

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

5. The following code attempts to search for a value in a BST. Identify the line containing the subtle bug that can cause incorrect behavior or inefficiency.

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

medium

A. Line 5: left_search = searchBST(root.left, val)

B. Line 4: if root.val == val: return root

C. Line 2: if root is None: return None

D. Line 7: return searchBST(root.right, val)

Solution

1. Step 1: Understand the code logic

   This code searches both left and right subtrees regardless of BST property.

2. Step 2: Identify inefficiency bug

   Line 5 always searches left subtree even if val > root.val, ignoring BST property and causing O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring BST property causes unnecessary subtree searches [OK]

Hint: Searching both subtrees ignores BST property [OK]

Common Mistakes:

• Not pruning search using BST property