Two Sum IV - Input is a BST

Given the reference to the root of a binary search tree and a target value, return whether or not two individual values within the tree can sum to the target.

Note: You may assume there are no duplicate values in the tree.

Example(s)

Example 1:

Input:
   1
  / \
 2   3
target = 4

Output: true
Explanation: 1 + 3 = 4

Example 2:

Input:
   1
  / \
 2   3
target = 7

Output: false
Explanation: No two values sum to 7 (max sum is 1 + 3 = 4)

Example 3:

Input:
      5
    /   \
   3     6
  / \     \
 2   4     7
target = 9

Output: true
Explanation: 2 + 7 = 9 or 5 + 4 = 9

Example 4:

Input:
      5
    /   \
   3     6
  / \     \
 2   4     7
target = 28

Output: false
Explanation: No two values sum to 28

Solution

There are multiple approaches:

1. Hash Set approach: Traverse the tree and use a hash set to track seen values
2. In-order + Two Pointers: Convert BST to sorted array, then use two pointers
3. DFS with Hash Set: Similar to hash set but using DFS traversal

JavaScript Solution

JavaScript Solution - Hash Set

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Check if two nodes in BST sum to target
* @param {TreeNode} root - Root of the BST
* @param {number} target - Target sum
* @return {boolean} - True if two nodes sum to target
*/
function findTarget(root, target) {
const seen = new Set();

/**
 * DFS helper function
 * @param {TreeNode} node - Current node
 * @return {boolean} - True if complement found
 */
function dfs(node) {
  if (!node) return false;
  
  // Check if complement exists
  const complement = target - node.val;
  if (seen.has(complement)) {
    return true;
  }
  
  // Add current value to set
  seen.add(node.val);
  
  // Recursively check left and right subtrees
  return dfs(node.left) || dfs(node.right);
}

return dfs(root);
}

// Helper function to create a tree node
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

// Test case 1: [1, 2, 3], target = 4
const tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);
console.log('Example 1:', findTarget(tree1, 4)); // true

// Test case 2: [1, 2, 3], target = 7
const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);
console.log('Example 2:', findTarget(tree2, 7)); // false

// Test case 3: [5, 3, 6, 2, 4, null, 7], target = 9
const tree3 = new TreeNode(5);
tree3.left = new TreeNode(3);
tree3.right = new TreeNode(6);
tree3.left.left = new TreeNode(2);
tree3.left.right = new TreeNode(4);
tree3.right.right = new TreeNode(7);
console.log('Example 3:', findTarget(tree3, 9)); // true

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Hash Set

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def find_target(root: Optional[TreeNode], target: int) -> bool:
  """
  Check if two nodes in BST sum to target
  
  Args:
      root: Root of the BST
      target: Target sum
      
  Returns:
      bool: True if two nodes sum to target
  """
  seen = set()
  
  def dfs(node: Optional[TreeNode]) -> bool:
      """
      DFS helper function
      
      Returns:
          bool: True if complement found
      """
      if not node:
          return False
      
      # Check if complement exists
      complement = target - node.val
      if complement in seen:
          return True
      
      # Add current value to set
      seen.add(node.val)
      
      # Recursively check left and right subtrees
      return dfs(node.left) or dfs(node.right)
  
  return dfs(root)

# Test case 1: [1, 2, 3], target = 4
tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(3)
print('Example 1:', find_target(tree1, 4))  # True

# Test case 2: [1, 2, 3], target = 7
tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(3)
print('Example 2:', find_target(tree2, 7))  # False

# Test case 3: [5, 3, 6, 2, 4, None, 7], target = 9
tree3 = TreeNode(5)
tree3.left = TreeNode(3)
tree3.right = TreeNode(6)
tree3.left.left = TreeNode(2)
tree3.left.right = TreeNode(4)
tree3.right.right = TreeNode(7)
print('Example 3:', find_target(tree3, 9))  # True

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (In-Order + Two Pointers)

Here's an approach that leverages the BST property by converting to a sorted array:

JavaScript In-Order

/**
 * Alternative: In-order traversal + Two pointers
 * Leverages BST property to get sorted array
 */
function findTargetInOrder(root, target) {
  // Step 1: Convert BST to sorted array using in-order traversal
  const values = [];
  
  function inOrder(node) {
    if (!node) return;
    inOrder(node.left);
    values.push(node.val);
    inOrder(node.right);
  }
  
  inOrder(root);
  
  // Step 2: Two pointers on sorted array
  let left = 0;
  let right = values.length - 1;
  
  while (left < right) {
    const sum = values[left] + values[right];
    
    if (sum === target) {
      return true;
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  
  return false;
}

Python In-Order

def find_target_in_order(root: Optional[TreeNode], target: int) -> bool:
    """
    Alternative: In-order traversal + Two pointers
    """
    # Step 1: Convert BST to sorted array using in-order traversal
    values = []
    
    def in_order(node: Optional[TreeNode]):
        if not node:
            return
        in_order(node.left)
        values.append(node.val)
        in_order(node.right)
    
    in_order(root)
    
    # Step 2: Two pointers on sorted array
    left = 0
    right = len(values) - 1
    
    while left < right:
        total = values[left] + values[right]
        
        if total == target:
            return True
        elif total < target:
            left += 1
        else:
            right -= 1
    
    return False

Alternative: BFS with Hash Set

Here's a BFS (level-order) approach:

JavaScript BFS

/**
 * BFS approach with hash set
 */
function findTargetBFS(root, target) {
  if (!root) return false;
  
  const seen = new Set();
  const queue = [root];
  
  while (queue.length > 0) {
    const node = queue.shift();
    const complement = target - node.val;
    
    if (seen.has(complement)) {
      return true;
    }
    
    seen.add(node.val);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return false;
}

Python BFS

from collections import deque

def find_target_bfs(root: Optional[TreeNode], target: int) -> bool:
    """
    BFS approach with hash set
    """
    if not root:
        return False
    
    seen = set()
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        complement = target - node.val
        
        if complement in seen:
            return True
        
        seen.add(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return False

Complexity

• Time Complexity:
  • Hash Set (DFS/BFS): O(n) - Where n is the number of nodes. We visit each node once.
  • In-Order + Two Pointers: O(n) - In-order traversal is O(n), two pointers is O(n).
• Space Complexity:
  • Hash Set (DFS/BFS): O(n) - For the hash set and recursion stack (or queue).
  • In-Order + Two Pointers: O(n) - For storing the sorted array.

Approach

The solution uses a hash set with DFS traversal:

1. Traverse the tree: Use DFS (or BFS) to visit each node
2. Check complement: For each node value, check if target - node.val exists in the set
3. Add to set: Add current node value to the set
4. Recursive calls: Continue with left and right children
5. Return result: Return true if complement found, false otherwise

Key Insights

• Hash set approach: Similar to regular two sum problem
• BST property not required: Hash set approach works for any binary tree
• In-order + two pointers: Leverages BST property for sorted array
• O(n) time: Optimal time complexity
• Early termination: Can return as soon as complement is found

Step-by-Step Example

Let's trace through Example 1: target = 4, tree with nodes [1, 2, 3]

Tree:
   1
  / \
 2   3

DFS traversal:

Node 1:
  complement = 4 - 1 = 3
  seen.has(3)? No (empty set)
  seen.add(1) → {1}
  Check left child: node 2

Node 2:
  complement = 4 - 2 = 2
  seen.has(2)? No
  seen.add(2) → {1, 2}
  Check left child: null
  Check right child: null
  Return to node 1

Node 1 (continue):
  Check right child: node 3

Node 3:
  complement = 4 - 3 = 1
  seen.has(1)? Yes! → Return true

Result: true (1 + 3 = 4)

Visual Representation

Tree:          DFS with Hash Set:
   1           Node 1: complement = 3, not in { }
  / \          seen = {1}
 2   3         Node 2: complement = 2, not in {1}
               seen = {1, 2}
               Node 3: complement = 1, found in {1, 2} ✓
               Return true

Edge Cases

• Empty tree: Return false
• Single node: Return false (need two nodes)
• No solution: Return false
• Target equals twice a value: Only works if that value appears twice (but problem says no duplicates)
• Negative values: Works correctly
• Large target: Works correctly

Important Notes

• No duplicates: Problem states no duplicate values
• Two different nodes: Must be two distinct nodes (not the same node twice)
• BST property: Not strictly necessary for hash set approach, but useful for in-order approach
• Any traversal: DFS, BFS, or in-order all work with hash set

Comparison of Approaches

Approach	Time	Space	Notes
Hash Set (DFS)	O(n)	O(n)	Simple, works for any tree
Hash Set (BFS)	O(n)	O(n)	Level-order traversal
In-Order + Two Pointers	O(n)	O(n)	Leverages BST property

Related Problems

• Two Sum: Array version
• Two Sum II - Input Array is Sorted: Sorted array version
• Two Sum III - Data Structure Design: Design a data structure
• Three Sum: Extension to three numbers

Takeaways

• Hash set approach is simple and works for any binary tree
• BST property can be leveraged for in-order + two pointers
• O(n) time is optimal (must visit all nodes in worst case)
• Early termination possible when complement is found
• Similar to array two sum but with tree traversal