Leetcode 653. Two Sum IV - Input is a BST

Problem

We are given a binary search tree (BST) and a target value and we need to find out if there exist two elements in the BST such that their sum is equal to the target value.

Example

For example, let's consider the following BST and target.

Input BST:

15

/
3 6 / \
2 4 7

Target = 9

In this case, there exist two nodes 2 and 7, which sum up to the target value 9. Hence, the function should return TRUE.

Approach

To solve this problem, we can use bidirectional in-order depth-first search (DFS) which is optimized for BST, as the inorder traversal of a BST gives us a sorted order. If the BST was instead a plain binary tree, we would need to traverse the whole tree, sort the values, and then apply the two-pointer technique, which would not be optimal.

The given solution initializes two spirals, one from left to right (increasing order) and the other from right to left (decreasing order). We then get the next number from each spiral and add them. If the sum is equal to the target, we return true. If the sum is less than the target, we move the left spiral. If the sum is greater than the target, we move the right spiral.

Steps

For the Input BST

1
2
3    5
4   / \
5  3   6
6 / \   \
72   4   7
  • Initialize left spiral and right spiral
  • Get next number from each spiral ie., 2 and 7
  • Sum = 2 + 7 = 9
  • If Sum is equal to target i.e., 9, return True
  • If Sum is less than target, move the left spiral to next
  • If Sum is greater than target, move the right spiral to next

Solution

Python

1
2python
3class Solution:
4    def findTarget(self, root: TreeNode, k: int) -> bool:
5        inorder = []
6        self.inOrder(root, inorder)
7        left, right = 0, len(inorder)-1
8        while left < right:
9            if inorder[left] + inorder[right] == k:
10                return True
11            elif inorder[left] + inorder[right] < k:
12                left += 1
13            else:
14                right -= 1
15        return False
16
17    def inOrder(self, root, inorder):
18        if root is None:
19            return
20        self.inOrder(root.left, inorder)
21        inorder.append(root.val)
22        self.inOrder(root.right, inorder)

Java

1
2java
3class Solution {
4    public boolean findTarget(TreeNode root, int k) {
5        ArrayList<Integer> nums = new ArrayList<>();
6        inorder(root, nums);
7        for(int i = 0, j = nums.size()-1; i<j;){
8            if(nums.get(i) + nums.get(j) == k)return true;
9            if(nums.get(i) + nums.get(j) < k)i++;
10            else j--;
11        }
12        return false;
13    }
14
15    void inorder(TreeNode root, ArrayList<Integer> nums){
16        if(root == null)return;
17        inorder(root.left, nums);
18        nums.add(root.val);
19        inorder(root.right, nums);
20    }
21}

Javascript

1
2javascript
3var findTarget = function(root, k) {
4    let values = new Set(),
5        stack = [root];
6        
7    while (stack.length) {
8        let node = stack.pop();
9        
10        if (values.has(k - node.val)) return true;
11        values.add(node.val);
12        
13        if (node.right) stack.push(node.right);
14        if (node.left) stack.push(node.left);
15    }
16    return false;
17};

C++

1
2cpp
3class Solution {
4public:
5    bool findTarget(TreeNode* root, int k) {
6        unordered_set<int> s;
7        return dfs(root, s, k);
8    }
9    
10    bool dfs(TreeNode* root, unordered_set<int>& s, int k) {
11        if (!root) return false;
12        if (s.count(k - root -> val)) return true;
13        s.insert(root -> val);
14        return dfs(root -> left, s, k) || dfs(root -> right, s, k);
15    }
16};

C#

1
2csharp
3public class Solution {
4    HashSet<int> nodes = new HashSet<int>();
5    public bool FindTarget(TreeNode root, int k) {
6        if (root == null) return false;
7        if (nodes.Contains(k - root.val)) return true;
8        nodes.Add(root.val);
9        return FindTarget(root.left, k) || FindTarget(root.right, k);
10    }
11}

In the code above, for Python, Java, JavaScript, C++ and C#, we traverse the tree using recursive in-order Depth-First Search (DFS), store the nodes in a hash set (or an array for Python and Java), and then perform a search to see if the sum of two numbers equals the target value.

In Python and Java, we create two pointers, left and right, and move them towards each other while checking for the sum. If the sum is smaller than the target, we move the left pointer to increase the sum. If the sum is higher than the target, we move the right pointer to reduce the sum. If the sum is equal to the target, we return True. This takes advantage of the fact that an in-order traversal of a BST will result in sorted numbers.

The JavaScript, C++ and C# versions are slightly different in that they do not sort the numbers using in-order traversal. Instead, they use DFS to traverse the tree, storing each number in a set, then checking whether the difference of the target and the current number has appeared before. If it has, that means there are two numbers whose sum is equal to the target, and the function should return True.

The overall time complexity for these solutions is O(n), where n is the number of nodes in the tree, because we need to traverse all the nodes. The space complexity is also O(n) for storing the values of the nodes. If the BST is balanced, the depth of recursive stack would be logged and thus the space complexity would be O(logn).

Finally, do not forget to handle the case where the BST is empty. In this situation, the function should return False because there are no two numbers that can sum up to the target.

And that concludes the solution for finding two elements in a BST that sum up to a target value.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫