Two Sum IV - Input is a BST

Easy

#0607Time: 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.2 companies

Patterns

Two Pointers

Algorithms

Depth-First Search Breadth-First Search

Data structures

Hash Table Tree Binary Tree Binary Search Tree

Companies

Cisco Samsung

Prompt

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:

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

Example 2:

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, 10⁴].
-10⁴ <= Node.val <= 10⁴
root is guaranteed to be a valid binary search tree.
-10⁵ <= k <= 10⁵

Approaches

4 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean findTarget(TreeNode root, int k) {18        List<Integer> list = new ArrayList<>();19        inorder(root, list);20        int left = 0;21        int right = list.size() - 1;22        while (left < right) {23            int sum = list.get(left) + list.get(right);24            if (sum == k) {25                return true;26            } else if (sum < k) {27                left++;28            } else {29                right--;30            }31        }32        return false;33    }34 35    private void inorder(TreeNode root, List<Integer> list) {36        if (root == null) {37            return;38        }39        inorder(root.left, list);40        list.add(root.val);41        inorder(root.right, list);42    }43}

Complexity

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.

Trade-offs

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

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.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean findTarget(TreeNode root, int k) {18        List<Integer> list = new ArrayList<>();19        inorder(root, list);20        for (int i = 0; i < list.size(); i++) {21            for (int j = i + 1; j < list.size(); j++) {22                if (list.get(i) + list.get(j) == k) {23                    return true;24                }25            }26        }27        return false;28    }29 30    private void inorder(TreeNode root, List<Integer> list) {31        if (root == null) {32            return;33        }34        inorder(root.left, list);35        list.add(root.val);36        inorder(root.right, list);37    }38}

Complexity

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

Trade-offs

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.

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.

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

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean findTarget(TreeNode root, int k) {18        Set<Integer> set = new HashSet<>();19        return find(root, k, set);20    }21 22    private boolean find(TreeNode node, int k, Set<Integer> set) {23        if (node == null) {24            return false;25        }26        if (set.contains(k - node.val)) {27            return true;28        }29        set.add(node.val);30        return find(node.left, k, set) || find(node.right, k, set);31    }32}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean findTarget(TreeNode root, int k) {18        if (root == null) return false;19        20        Stack<TreeNode> leftStack = new Stack<>();21        Stack<TreeNode> rightStack = new Stack<>();22        23        pushLeft(leftStack, root);24        pushRight(rightStack, root);25        26        TreeNode leftNode = nextLeft(leftStack);27        TreeNode rightNode = nextRight(rightStack);28        29        while (leftNode != null && rightNode != null && leftNode.val < rightNode.val) {30            int sum = leftNode.val + rightNode.val;31            if (sum == k) {32                return true;33            } else if (sum < k) {34                leftNode = nextLeft(leftStack);35            } else { // sum > k36                rightNode = nextRight(rightStack);37            }38        }39        40        return false;41    }42    43    private void pushLeft(Stack<TreeNode> stack, TreeNode node) {44        while (node != null) {45            stack.push(node);46            node = node.left;47        }48    }49    50    private void pushRight(Stack<TreeNode> stack, TreeNode node) {51        while (node != null) {52            stack.push(node);53            node = node.right;54        }55    }56    57    private TreeNode nextLeft(Stack<TreeNode> stack) {58        if (stack.isEmpty()) return null;59        TreeNode node = stack.pop();60        pushLeft(stack, node.right);61        return node;62    }63    64    private TreeNode nextRight(Stack<TreeNode> stack) {65        if (stack.isEmpty()) return null;66        TreeNode node = stack.pop();67        pushRight(stack, node.left);68        return node;69    }70}

Complexity

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

Trade-offs

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.

Solutions

Solution

1/** * 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 ); } }

1/** * 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 ); } };

1class 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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * 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 ); } }

1/** * 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 ); } };

1class 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 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.