# Two Sum IV - Input is a BST
**Difficulty:** EASY
[External](https://leetcode.com/problems/two-sum-iv-input-is-a-bst)
Canonical: https://scaleengineer.com/dsa/problems/two-sum-iv-input-is-a-bst
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree, Binary Search Tree
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
Given the `root` of a binary search tree and an integer `k`, return `true` _if there exist two elements in the BST such that their sum is equal to_ `k`, _or_ `false` _otherwise_.

**Example 1:**

![](https://assets.glich.co/dsa/two-sum-iv-input-is-a-bst/image0.jpg) 

**Input:** root = [5,3,6,2,4,null,7], k = 9
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/two-sum-iv-input-is-a-bst/image1.jpg) 

**Input:** root = [5,3,6,2,4,null,7], k = 28
**Output:** false

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `-104 <= Node.val <= 104`
* `root` is guaranteed to be a **valid** binary search tree.
* `-105 <= k <= 105`

# Approaches
## Brute Force with List Conversion
This approach first converts the Binary Search Tree into a list of its values. Any traversal method can be used to populate the list. After creating the list, we use a pair of nested loops to check every possible pair of elements to see if their sum equals the target `k`.
**Time:** O(N^2), where N is the number of nodes. The in-order traversal takes O(N) time. The nested loops take O(N^2) time. Thus, the total time complexity is dominated by the nested loops. · **Space:** O(N) to store the list of node values. The recursion stack for the in-order traversal also takes O(H) space, where H is the height of the tree, which is O(N) in the worst case. So, the total space is O(N).
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient in terms of time complexity (O(N^2)), making it unsuitable for large trees.; Does not effectively utilize the properties of a BST beyond the initial traversal.
### Explanation
First, we define a helper function to perform a traversal of the BST (e.g., in-order). During the traversal, we add each node's value to a dynamic list. After the traversal is complete, we have a list containing all the node values from the tree. We then iterate through this list with a nested loop. The outer loop runs from the first element to the second-to-last, and the inner loop runs from the next element to the last. For each pair of elements `(list[i], list[j])`, we check if their sum is equal to `k`. If we find such a pair, we immediately return `true`. If the loops complete without finding any such pair, it means no solution exists, and we return `false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) + list.get(j) == k) {
                    return true;
                }
            }
        }
        return false;
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}
```
### Algorithm
- Create an empty list, say `values`.
- Perform an in-order traversal of the BST. For each node visited, add its value to the `values` list.
- Iterate through the `values` list with an index `i` from `0` to `values.size() - 1`.
- Inside this loop, iterate with an index `j` from `i + 1` to `values.size() - 1`.
- Check if `values.get(i) + values.get(j) == k`.
- If the condition is true, return `true`.
- If the loops complete, return `false`.

## Traversal with a Hash Set
This approach improves upon the brute-force method by using a hash set to achieve a linear time complexity. We traverse the tree once, and for each node, we check if its complement (`k - node.val`) exists in the hash set. If it does, we've found a pair. If not, we add the current node's value to the set and continue.
**Time:** O(N), where N is the number of nodes. We visit each node in the tree exactly once. For each node, the hash set operations (lookup and insertion) take, on average, O(1) time. · **Space:** O(N). In the worst case, the hash set might store all N node values. The recursion stack also contributes O(H) space, which is O(N) in the worst case of a skewed tree.
**Pros:** Time-efficient with a linear O(N) time complexity.; Relatively simple to implement.
**Cons:** Requires extra space proportional to the number of nodes in the tree.
### Explanation
We initialize an empty hash set. We then traverse the tree using any standard traversal method (DFS or BFS are both suitable). For this example, we'll use a recursive DFS approach. We define a helper function, say `find(node, k, set)`. In this function, for the current `node`, we first check if the node is `null`, in which case we return `false`. Then, we check if the complement, `k - node.val`, is present in the hash set. If it is, we have found a valid pair, and we return `true`. If the complement is not found, we add the current node's value, `node.val`, to the hash set to make it available for future checks. Finally, we recursively call the `find` function for the left and right children. If either of these recursive calls returns `true`, we propagate `true` up the call stack. If the entire tree is traversed and no pair is found, the initial call will return `false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return find(root, k, set);
    }

    private boolean find(TreeNode node, int k, Set<Integer> set) {
        if (node == null) {
            return false;
        }
        if (set.contains(k - node.val)) {
            return true;
        }
        set.add(node.val);
        return find(node.left, k, set) || find(node.right, k, set);
    }
}
```
### Algorithm
- Create an empty hash set, `set`.
- Define a recursive function `traverse(node, k, set)`.
- Base case: If `node` is `null`, return `false`.
- Check if `set` contains the complement `k - node.val`. If yes, return `true`.
- Add `node.val` to the `set`.
- Recursively call `traverse` on the left child and then the right child.
- Return `true` if either of the recursive calls returns `true`, otherwise `false`.
- Start the process by calling `traverse(root, k, set)`.

## In-order Traversal with Two Pointers
This approach leverages the property that an in-order traversal of a BST results in a sorted sequence of values. We first perform an in-order traversal to get a sorted list of all node values. Then, we apply the classic two-pointer technique on this sorted list to find a pair that sums to `k`.
**Time:** O(N). The in-order traversal takes O(N) time. The two-pointer scan on the resulting list also takes O(N) time. The total time complexity is O(N). · **Space:** O(N). We need O(N) space to store the list of node values. The recursion stack for the traversal also takes O(H) space, which can be O(N) in the worst case.
**Pros:** Efficient O(N) time complexity.; It's a classic pattern combining tree traversal with array algorithms.
**Cons:** Requires O(N) extra space, which is the same as the hash set approach.; Performs two passes over the data (one to build the list, one to find the sum).
### Explanation
First, we perform an in-order traversal of the BST and store all the node values in a list. Because it's an in-order traversal of a BST, this list will be sorted in ascending order. After obtaining the sorted list, we initialize two pointers: `left` at the beginning of the list (index 0) and `right` at the end of the list (index `list.size() - 1`). We enter a loop that continues as long as `left` is less than `right`. Inside the loop, we calculate the sum of the values at the two pointers. If the sum equals `k`, we've found our pair and return `true`. If the sum is less than `k`, we need a larger sum, so we move the `left` pointer one step to the right (`left++`). If the sum is greater than `k`, we need a smaller sum, so we move the `right` pointer one step to the left (`right--`). If the loop finishes without finding a pair, we return `false`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int sum = list.get(left) + list.get(right);
            if (sum == k) {
                return true;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}
```
### Algorithm
- Create an empty list, `sortedList`.
- Perform an in-order traversal on the BST and populate `sortedList`.
- Initialize `left = 0` and `right = sortedList.size() - 1`.
- While `left < right`:
  - Calculate `sum = sortedList.get(left) + sortedList.get(right)`.
  - If `sum == k`, return `true`.
  - If `sum < k`, increment `left`.
  - If `sum > k`, decrement `right`.
- If the loop terminates, return `false`.

## Space-Optimized Two Pointers with BST Iterators
This is the most optimized approach in terms of space. It combines the logic of the two-pointer technique with an in-place traversal of the BST, avoiding the need to store all nodes in an auxiliary data structure. It uses two iterators, one for forward in-order traversal (to get the smallest elements) and one for reverse in-order traversal (to get the largest elements), effectively simulating the two pointers on a sorted list without creating the list itself.
**Time:** O(N). In the worst case, we traverse each node once. Each node is pushed onto and popped from a stack at most once. · **Space:** O(H), where H is the height of the tree. This is the space required for the two stacks. For a balanced BST, this is O(log N), which is a significant improvement over O(N). For a skewed tree, it degrades to O(N).
**Pros:** Most space-efficient solution, especially for balanced trees (O(log N) space).; Maintains an efficient linear time complexity.
**Cons:** More complex to implement compared to the other approaches.
### Explanation
The core idea is to get the next smallest element and the next largest element from the BST on the fly. This is achieved by using two stacks to simulate two simultaneous traversals.
- One stack (`leftStack`) manages a standard in-order traversal. It's initialized by pushing the root and all its left descendants. To get the next smallest element, we pop from this stack.
- The second stack (`rightStack`) manages a reverse in-order traversal (Right-Root-Left). It's initialized by pushing the root and all its right descendants. To get the next largest element, we pop from this stack.

We start by getting the smallest element (`leftNode`) and the largest element (`rightNode`). We then loop as long as these two nodes are not the same. Inside the loop, we check their sum. If `sum == k`, we return `true`. If `sum < k`, we advance to the next smallest element by using the `leftStack`. If `sum > k`, we advance to the next largest element using the `rightStack`. This process continues until the pointers cross, at which point we can conclude no such pair exists.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        
        Stack<TreeNode> leftStack = new Stack<>();
        Stack<TreeNode> rightStack = new Stack<>();
        
        pushLeft(leftStack, root);
        pushRight(rightStack, root);
        
        TreeNode leftNode = nextLeft(leftStack);
        TreeNode rightNode = nextRight(rightStack);
        
        while (leftNode != null && rightNode != null && leftNode.val < rightNode.val) {
            int sum = leftNode.val + rightNode.val;
            if (sum == k) {
                return true;
            } else if (sum < k) {
                leftNode = nextLeft(leftStack);
            } else { // sum > k
                rightNode = nextRight(rightStack);
            }
        }
        
        return false;
    }
    
    private void pushLeft(Stack<TreeNode> stack, TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    private void pushRight(Stack<TreeNode> stack, TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
    }
    
    private TreeNode nextLeft(Stack<TreeNode> stack) {
        if (stack.isEmpty()) return null;
        TreeNode node = stack.pop();
        pushLeft(stack, node.right);
        return node;
    }
    
    private TreeNode nextRight(Stack<TreeNode> stack) {
        if (stack.isEmpty()) return null;
        TreeNode node = stack.pop();
        pushRight(stack, node.left);
        return node;
    }
}
```
### Algorithm
- Implement two mechanisms for BST iteration: one for forward in-order and one for reverse in-order, both using a stack.
- The forward iterator stack is initialized by pushing the root and all its left children.
- The reverse iterator stack is initialized by pushing the root and all its right children.
- Get the initial smallest value `l` and largest value `r` from the respective iterators.
- Loop while `l < r`:
  - If `l + r == k`, return `true`.
  - If `l + r < k`, get the next smallest value for `l`.
  - If `l + r > k`, get the next largest value for `r`.
- If the loop completes, return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Two_Sum_IV_Input_is_a_BST { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/ public class Solution_queue { public boolean findTarget ( TreeNode root , int k ) { Set < Integer > set = new HashSet <>(); Queue < TreeNode > queue = new LinkedList <>(); queue . add ( root ); while (! queue . isEmpty ()) { if ( queue . peek () != null ) { TreeNode node = queue . remove (); if ( set . contains ( k - node . val )) return true ; set . add ( node . val ); queue . add ( node . right ); queue . add ( node . left ); } else queue . remove (); } return false ; } } // time: O(N) // space: O(N) public class Solution_usingBST { // inorder traversal to get sorted list public boolean findTarget ( TreeNode root , int k ) { List < Integer > list = new ArrayList <>(); inorder ( root , list ); int l = 0 , r = list . size () - 1 ; while ( l < r ) { int sum = list . get ( l ) + list . get ( r ); if ( sum == k ) return true ; if ( sum < k ) l ++; else r --; } return false ; } public void inorder ( TreeNode root , List < Integer > list ) { if ( root == null ) return ; inorder ( root . left , list ); list . add ( root . val ); inorder ( root . right , list ); } } // time: O(N) // space: O(N) public class Solution { public boolean findTarget ( TreeNode root , int k ) { Set < Integer > set = new HashSet (); return find ( root , k , set ); } public boolean find ( TreeNode root , int k , Set < Integer > set ) { if ( root == null ) { return false ; } if ( set . contains ( k - root . val )) { return true ; } set . add ( root . val ); return find ( root . left , k , set ) || find ( root . right , k , set ); } } } ////// class Solution { private Set < Integer > vis = new HashSet <>(); private int k ; public boolean findTarget ( TreeNode root , int k ) { this . k = k ; return dfs ( root ); } private boolean dfs ( TreeNode root ) { if ( root == null ) { return false ; } if ( vis . contains ( k - root . val )) { return true ; } vis . add ( root . val ); return dfs ( root . left ) || dfs ( root . right ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool findTarget ( TreeNode * root , int k ) { unordered_set < int > vis ; function < bool ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return false ; } if ( vis . count ( k - root -> val )) { return true ; } vis . insert ( root -> val ); return dfs ( root -> left ) || dfs ( root -> right ); }; return dfs ( root ); } };
```

### Python

```python
class BSTIterator : def __init__ ( self , root : Optional [ TreeNode ], leftToRight : bool ): self . stack = [] self . leftToRight = leftToRight self . _pushUntilNone ( root ) def next ( self ) -> int : node = self . stack . pop () if self . leftToRight : self . _pushUntilNone ( node . right ) else : self . _pushUntilNone ( node . left ) return node . val # if passed in a None node, then None will not be pushed to stack def _pushUntilNone ( self , root : Optional [ TreeNode ]): while root : self . stack . append ( root ) root = root . left if self . leftToRight else root . right class Solution : def findTarget ( self , root : Optional [ TreeNode ], k : int ) -> bool : if not root : return False left = BSTIterator ( root , True ) right = BSTIterator ( root , False ) l = left . next () r = right . next () while l < r : summ = l + r if summ == k : return True if summ < k : l = left . next () else : r = right . next () return False ########### # 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 class Solution : def findTarget ( self , root : Optional [ TreeNode ], k : int ) -> bool : def dfs ( root ): if root is None : return False if k - root . val in vis : return True vis . add ( root . val ) return dfs ( root . left ) or dfs ( root . right ) vis = set () return dfs ( root )
```