Two Sum IV - Input is a BST
An easy BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 1
- Core for
- 2 roles
The problem
Given a binary search tree and a number target, decide whether two different nodes of the tree hold values that add up to target. The same node cannot be used twice.
Example 1
- Input
- root=[7,4,9,2,5,null,11], k=13
- Output
- true
- Why
- 4 + 9 = 13.
Example 2
- Input
- root=[7,4,9,2,5,null,11], k=25
- Output
- false
- Why
- Even the two largest values, 9 and 11, only reach 20.
Example 3
- Input
- root=[2,1,3], k=4
- Output
- true
- Why
- Elements 1+3=4.
Constraints
- The number of nodes is in the range [1, 104].
- -105 <= Node.val <= 105
- -109 <= k <= 109
How to think about it
Updated 2026-09-29Two-sum on an array uses two pointers converging from opposite ends once elements are sorted. A BST is already sorted: an ascending iterator walking forward from the minimum and a descending iterator walking backward from the maximum simulate the exact same two-pointer squeeze directly on the tree.
Approaches, worst first
Hash set traversal
time O(n) · space O(n)
Visit every node using any standard traversal, checking whether `k - node.val` is in a hash set before inserting `node.val`. Completely ignores the BST ordering, taking full linear memory regardless of tree height.
Inorder array two-pointer
time O(n) · space O(n)
Dump the inorder traversal into an array to obtain a sorted list, then pinch inward with left and right pointers. Clean and optimal in time, but buffers all n elements upfront.
Two BST iteratorsWrite this one
time O(n) · space O(h)
Instantiate two stack-based iterators: one moving forward (left-root-right) and one moving backward (right-root-left). Advance the forward pointer when the pair sum is too small and the backward pointer when too large, halting when they meet.
Where people lose marks · 2
- Reusing a single node. When `2 * node.val == k`, an unchecked hash set or pointer logic can pair a node with itself if the presence check happens after insertion.
- Single-node tree edge case: a BST with only one node can never form a pair; the loop must terminate safely and return false.
Full solution
C++
#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
bool findTarget(TreeNode* root, int k) {
unordered_set<int> seen;
stack<TreeNode*> st;
if (root) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (seen.count(k - node->val)) return true;
seen.insert(node->val);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return false;
}
Java
import java.util.*;
public class Main {
static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
static boolean findTarget(TreeNode root, int k) {
Set<Integer> seen = new HashSet<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (seen.contains(k - node.val)) return true;
seen.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return false;
}
}
Python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_target(root, k):
seen = set()
stack = [root] if root else []
while stack:
node = stack.pop()
if (k - node.val) in seen:
return True
seen.add(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return False
JavaScript
function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
function findTarget(root, k) {
const vals = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
vals.push(node.val);
inorder(node.right);
}
inorder(root);
let l = 0, r = vals.length - 1;
while (l < r) {
const sum = vals[l] + vals[r];
if (sum === k) return true;
if (sum < k) l++;
else r--;
}
return false;
}
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .