Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The inorder traversal of a BST is a sorted list.
  2. 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");
    }
}

Solve Two Sum in a BST online · All practice problems