Scale Engineer

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 SearchBreadth-First Search
Data structures
Hash TableTreeBinary TreeBinary Search Tree
Companies
CiscoSamsung

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

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.

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

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

Solutions

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

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 →

Next problem