Two Sum in BST in DSA Python - Time & Space Complexity

Time Complexity: Two Sum in BST

O(n)

Understanding Time Complexity

We want to know how the time needed to find two numbers that add up to a target grows as the tree gets bigger.

How does the number of steps change when the BST has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def find_target(root, k):
    seen = set()
    def dfs(node):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)
    

This code checks if there are two numbers in the BST that add up to k by walking through the tree once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive depth-first search (DFS) visiting each node once.
• How many times: Once per node, so n times for n nodes.

How Execution Grows With Input

As the tree grows, the function visits each node once, so the steps grow directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The number of steps grows in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two numbers grows directly with the size of the tree.

Common Mistake

[X] Wrong: "Because the tree is sorted, we only need to check a few nodes, so it's faster than O(n)."

[OK] Correct: The code visits every node to be sure, so it still takes time proportional to all nodes.

Interview Connect

Understanding how to analyze recursive tree searches helps you explain your approach clearly and shows you know how your code scales.

Self-Check

"What if we used an in-order traversal to create a sorted list first, then used two pointers to find the sum? How would the time complexity change?"

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Find two nodes in a BST whose values add up to a target sum

B. Find the maximum value in a BST

C. Check if a BST is balanced

D. Count the number of nodes in a BST

Solution

1. Step 1: Understand the problem statement

   The problem asks to find two nodes in a Binary Search Tree (BST) such that their values add up to a given target sum.

2. Step 2: Identify the goal

   The goal is to find if such a pair exists, not to find max value, check balance, or count nodes.

3. Final Answer:

   Find two nodes in a BST whose values add up to a target sum -> Option A

4. Quick Check:

   Two Sum in BST means find pair with sum = target [OK]

Hint: Look for pairs adding to target in BST nodes [OK]

Common Mistakes:

• Confusing with finding max/min value
• Thinking it checks BST balance
• Assuming it counts nodes

2. Which of the following Python code snippets correctly initializes an empty set to store visited node values in a Two Sum in BST solution?

easy

A. visited = []

B. visited = set()

C. visited = {}

D. visited = ()

Solution

1. Step 1: Identify correct set initialization syntax

   In Python, set() creates an empty set. Using [] creates a list, {} creates an empty dictionary, and () creates an empty tuple.

2. Step 2: Confirm usage for visited nodes

   We need a set to quickly check if a complement value exists, so visited = set() is correct.

3. Final Answer:

   visited = set() -> Option B

4. Quick Check:

   Empty set = set() [OK]

Hint: Use set() to create empty set, not {} or [] [OK]

Common Mistakes:

• Using [] which creates a list, not a set
• Using {} which creates a dict, not a set
• Using () which creates a tuple

3. Given the BST below and target = 9, what will the function find_target(root, 9) return?

BST structure:
5
/ \
3 6
/ \ \
2 4 7

Code snippet:

def find_target(root, k):
    visited = set()
    def dfs(node):
        if not node:
            return False
        if k - node.val in visited:
            return True
        visited.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Trace DFS traversal and visited set updates

   Start at root 5: visited = {}. Check if 9-5=4 in visited? No. Add 5.
   Go left to 3: check 9-3=6 in visited? No. Add 3.
   Go left to 2: check 9-2=7 in visited? No. Add 2.
   Left and right of 2 are None, return False.
   Back to 3, go right to 4: check 9-4=5 in visited? Yes (5 is in visited). Return True.

2. Step 2: Confirm function returns True

   Since a pair (5,4) sums to 9, function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Pair (5,4) found = True [OK]

Hint: Check complements in visited set during DFS [OK]

Common Mistakes:

• Not updating visited set before recursive calls
• Returning False too early
• Confusing node values and complements

4. Identify the bug in the following code for Two Sum in BST and select the correct fix.

def find_target(root, k):
    visited = set()
    def dfs(node):
        if not node:
            return False
        if node.val in visited:
            return True
        visited.add(k - node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

medium

A. Check if node.val in visited, add (k - node.val) to visited

B. Check if node.val in visited, add node.val to visited

C. Check if (k - node.val) in visited, add (k - node.val) to visited

D. Check if (k - node.val) in visited, add node.val to visited

Solution

1. Step 1: Understand the logic for Two Sum in BST

   We must check if the complement (k - current node value) exists in visited set. If yes, return True. Then add current node value to visited.

2. Step 2: Identify the bug in code

   The code incorrectly checks if node.val is in visited and adds (k - node.val) to visited. This reverses the logic and causes wrong results.

3. Step 3: Correct fix

   Check if (k - node.val) in visited, then add node.val to visited.

4. Final Answer:

   Check if (k - node.val) in visited, add node.val to visited -> Option D

5. Quick Check:

   Check complement in visited, add current value [OK]

Hint: Check complement in visited, add current value [OK]

Common Mistakes:

• Swapping check and add values
• Adding complement instead of current value
• Checking current value instead of complement

5. You want to find if there exist two nodes in a BST that sum to a target value. Which approach is the most efficient in terms of time and space complexity?

hard

A. Check every pair of nodes by nested traversal (O(n²))

B. Use inorder traversal to get sorted list, then use two pointers to find sum

C. Use DFS with a hash set to check complements during traversal

D. Convert BST to a max heap and search pairs

Solution

1. Step 1: Analyze each approach

   Use DFS with a hash set to check complements during traversal: O(n) time and O(n) space.
   Use inorder traversal to get sorted list, then use two pointers to find sum: O(n) time and O(n) space.
   Check every pair of nodes by nested traversal (O(n²)): inefficient.
   Convert BST to a max heap and search pairs: unnecessary and costly.

2. Step 2: Choose the most efficient approach

   Both DFS with hash set and inorder + two pointers have O(n) time and space, but DFS with hash set uses less extra space by checking on the fly during traversal, avoiding full list creation.

3. Final Answer:

   Use DFS with a hash set to check complements during traversal -> Option C

4. Quick Check:

   DFS + hash set = efficient Two Sum in BST [OK]

Hint: Use DFS + hash set for O(n) time and space [OK]

Common Mistakes:

• Choosing nested loops causing O(n²) time
• Ignoring space complexity of inorder list
• Unnecessary BST conversions