Two Sum IV - Input is a BST

EASY

Description

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

Checkout 4 different approaches to solve Two Sum IV - Input is a BST. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Two Sum IV - Input is a BST. Click on different languages to view the code.

/** * 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 Solution

Watch the video walkthrough for Two Sum IV - Input is a BST

Algorithms:

Depth-First SearchBreadth-First Search

Patterns:

Two Pointers

Data Structures:

Hash TableTreeBinary TreeBinary Search Tree

Companies:

Cisco |Samsung |