Practice › Trees
Two Sum in a BST
Medium · Trees · Asked at Amazon, Microsoft, Meta
The tree is a BST with distinct values. Print YES if there are two different nodes whose values add up to target, otherwise NO.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node. Third line: target.
Output
YES or NO.
Constraints
- 1 ≤ number of nodes ≤ 10^4
The inorder traversal is sorted — use two pointers on it. Or keep a hash set while traversing.
Example 1
Input
7 5 3 6 2 4 -1 7 9
Output
YES
Example 2
Input
7 5 3 6 2 4 -1 7 28
Output
NO
Hints
- The inorder traversal of a BST is a sorted list.
- Run the classic two-pointer pair search on that sorted list (the two pointers never meet at the same node).
Approach
Collect the inorder sequence (sorted, distinct). Then l = 0, r = n − 1: if v[l] + v[r] equals the target, answer YES; if smaller, l++; if larger, r--. Stopping when l == r guarantees two different nodes. (A hash set during a traversal also works.)
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
vector<long long> v;
void inorder(Node *n) {
if (!n) return;
inorder(n->left);
v.push_back(n->val);
inorder(n->right);
}
int main() {
Node *root = readTree();
long long t;
cin >> t;
inorder(root);
int l = 0, r = (int)v.size() - 1;
while (l < r) {
long long s = v[l] + v[r];
if (s == t) {
cout << "YES\n";
return 0;
}
if (s < t) l++;
else r--;
}
cout << "NO\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
t, v, st, cur = rest[0], [], [], root
while cur or st:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
v.append(cur.val)
cur = cur.right
l, r, ans = 0, len(v) - 1, "NO"
while l < r:
s = v[l] + v[r]
if s == t:
ans = "YES"
break
if s < t:
l += 1
else:
r -= 1
print(ans)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static List<Long> v = new ArrayList<>();
static void inorder(Node n) {
if (n == null) return;
inorder(n.left);
v.add(n.val);
inorder(n.right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node root = readTree(sc);
long t = sc.nextLong();
inorder(root);
int l = 0, r = v.size() - 1;
while (l < r) {
long s = v.get(l) + v.get(r);
if (s == t) {
System.out.println("YES");
return;
}
if (s < t) l++;
else r--;
}
System.out.println("NO");
}
}