What happens if you not handling empty tree or single node tree edge cases?

Code may crash or return incorrect results Fix: Add base case checks for null root or single node

Interview Prepbinary-search-treeseasyAmazonGoogle

Two Sum IV in BST

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Two Sum IV in BST

easyTREEAmazonGoogle

Imagine you have a sorted collection of numbers stored in a binary search tree, and you want to quickly find if any two numbers add up to a target sum - like finding two friends whose combined ages match a given number.

💡 This problem tests your understanding of BST properties and how to efficiently search pairs that sum to a target. Beginners often struggle because they try naive pairwise comparisons without leveraging BST order or hashing, leading to inefficient solutions.

📋

Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to k, otherwise return false.

The number of nodes in the tree is in the range [1, 10^5].-10^4 <= Node.val <= 10^4-10^5 <= k <= 10^5

💡

Example

Input"root = [5,3,6,2,4,null,7], k = 9"

Outputtrue

Nodes with values 2 and 7 sum to 9.

Input"root = [5,3,6,2,4,null,7], k = 28"

Outputfalse

No two nodes sum to 28.

Single node tree → false
Tree with negative values and target sum involving negatives → true/false depending on nodes
Target sum equals twice a node's value but only one such node exists → false
Empty tree (null root) → false

⚠️

Common Mistakes

Using nested loops directly on BST nodes without inorder traversal

Leads to complex code and inefficient O(n^2) time with difficult debugging

✅ First convert BST to sorted array via inorder traversal, then apply pair checking

Checking if k - node.val equals node.val itself without ensuring distinct nodes

Incorrectly returns true when only one node matches half the target

✅ Ensure pairs are distinct nodes by checking different indices or nodes

Not handling empty tree or single node tree edge cases

Code may crash or return incorrect results

✅ Add base case checks for null root or single node

Using a hash set but forgetting to add current node's value before recursive calls

Misses valid pairs and returns false incorrectly

✅ Add current node's value to set before recursive calls

Using two-pointer approach on unsorted array (not from inorder traversal)

Two-pointer technique fails and returns wrong answer

✅ Always ensure array is sorted by inorder traversal before two-pointer

🧠

Brute Force (Inorder + Nested Loops)

💡 This approach exists to build intuition by trying all pairs explicitly. It is simple but inefficient, helping beginners understand the problem structure before optimizing.

Intuition

Traverse the BST to get a sorted list of values, then check every pair to see if any sums to k.

Algorithm

Perform an inorder traversal of the BST to get a sorted list of node values.
Use two nested loops to check every pair of values in the list.
If any pair sums to k, return true.
If no pairs sum to k after checking all, return false.

💡 The nested loops make the solution easy to understand but inefficient, which motivates better approaches.

</>

Code

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root: Optional[TreeNode], arr: List[int]) -> None:
    if root is None:
        return
    inorder(root.left, arr)
    arr.append(root.val)
    inorder(root.right, arr)

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    arr = []
    inorder(root, arr)
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == k:
                return True
    return False

# Example usage:
# root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, None, TreeNode(7)))
# print(findTarget(root, 9))  # Output: True

Line Notes

def inorder(root: Optional[TreeNode], arr: List[int]) -> None:Defines helper to collect BST values in sorted order

if root is None:Base case to stop recursion at leaf's child

arr.append(root.val)Add current node's value to the sorted list

for i in range(n):Outer loop picks first element for pair checking

for j in range(i + 1, n):Inner loop picks second element ensuring no repeats

if arr[i] + arr[j] == k:Check if current pair sums to target

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public void inorder(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorder(root.left, arr);
        arr.add(root.val);
        inorder(root.right, arr);
    }

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> arr = new ArrayList<>();
        inorder(root, arr);
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr.get(i) + arr.get(j) == k) return true;
            }
        }
        return false;
    }

    // Example main
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.findTarget(root, 9)); // true
    }
}

Line Notes

public void inorder(TreeNode root, List<Integer> arr)Helper to collect BST values in sorted order

if (root == null) return;Base case to stop recursion

arr.add(root.val);Add current node's value to list

for (int i = 0; i < n; i++) {Outer loop selects first element

for (int j = i + 1; j < n; j++) {Inner loop selects second element without repeats

if (arr.get(i) + arr.get(j) == k) return true;Check if pair sums to target

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}

bool findTarget(TreeNode* root, int k) {
    vector<int> arr;
    inorder(root, arr);
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == k) return true;
        }
    }
    return false;
}

// Example usage
int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);
    cout << (findTarget(root, 9) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

void inorder(TreeNode* root, vector<int>& arr)Helper to collect BST values in sorted order

if (!root) return;Base case for recursion termination

arr.push_back(root->val);Add current node's value to vector

for (int i = 0; i < n; i++) {Outer loop picks first element

for (int j = i + 1; j < n; j++) {Inner loop picks second element without repeats

if (arr[i] + arr[j] == k) return true;Check if pair sums to target

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorder(root, arr) {
    if (root === null) return;
    inorder(root.left, arr);
    arr.push(root.val);
    inorder(root.right, arr);
}

function findTarget(root, k) {
    const arr = [];
    inorder(root, arr);
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] === k) return true;
        }
    }
    return false;
}

// Example usage:
// const root = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)));
// console.log(findTarget(root, 9)); // true

Line Notes

function inorder(root, arr) {Helper to collect BST values in sorted order

if (root === null) return;Base case to stop recursion

arr.push(root.val);Add current node's value to array

for (let i = 0; i < n; i++) {Outer loop selects first element

for (let j = i + 1; j < n; j++) {Inner loop selects second element without repeats

if (arr[i] + arr[j] === k) return true;Check if pair sums to target

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Inorder traversal takes O(n), nested loops check O(n^2) pairs.

💡 For n=20 nodes, this means about 400 pair checks, which is inefficient for large trees.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is useful to demonstrate understanding before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n)`	No	N/A	Mention only - never code
2. Hash Set Lookup During DFS	`O(n)`	`O(n)`	Yes (due to recursion depth)	No	Good to code for fast solution
3. Inorder Traversal + Two Pointer	`O(n)`	`O(n)`	Yes (due to recursion depth)	No	Elegant and optimal, great to code

Practice

(1/5)

1. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace insertion path

Step 2: Check right child of 7

Final Answer:

Quick Check:

Solution

Step 1: Trace first tree (2,1,3)

Step 2: Trace second tree (5,1,4 with children 3 and 6)

Final Answer:

Quick Check:

Solution

Step 1: Understand BST height and search path

Step 2: Analyze worst-case time complexity

Final Answer:

Quick Check:

Solution

Step 1: Understand duplicates stored in right subtree

Step 2: Adapt deletion to remove all duplicates

Step 3: Why other options fail

Final Answer:

Quick Check:

Solution

Step 1: Understand variant allowing duplicates only on right subtree

Step 2: Modify comparison accordingly

Step 3: Reason why other options fail

Final Answer:

Quick Check: