Two Sum IV in BST

🎯

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

1. Perform an inorder traversal of the BST to get a sorted list of node values.
2. Use two nested loops to check every pair of values in the list.
3. If any pair sums to k, return true.
4. 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.

🧠

Hash Set Lookup During DFS

💡 This approach improves efficiency by checking complements on the fly using a hash set, avoiding nested loops and reducing time complexity.

Intuition

Traverse the BST and for each node, check if k - node.val exists in a hash set. If yes, return true; else add node.val to the set and continue.

Algorithm

1. Initialize an empty hash set to store visited node values.
2. Traverse the BST using DFS.
3. For each node, check if k - node.val is in the set.
4. If yes, return true; otherwise, add node.val to the set and continue.
5. If traversal ends without finding a pair, return false.

💡 This approach leverages hashing to reduce pair checking from O(n^2) to O(n).

</>

Code

from typing import Optional, Set

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

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    seen = set()
    def dfs(node: Optional[TreeNode]) -> bool:
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

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

Line Notes

seen = set()Initialize hash set to track visited values

def dfs(node: Optional[TreeNode]) -> bool:Define recursive DFS helper

if not node:Base case for recursion termination

if k - node.val in seen:Check if complement exists in set

seen.add(node.val)Add current node's value to set

return dfs(node.left) or dfs(node.right)Recurse left and right subtrees

import java.util.*;

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

public class Solution {
    Set<Integer> seen = new HashSet<>();

    public boolean dfs(TreeNode node, int k) {
        if (node == null) return false;
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left, k) || dfs(node.right, k);
    }

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, k);
    }

    // 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

Set<Integer> seen = new HashSet<>();Hash set to store visited node values

if (node == null) return false;Base case for recursion

if (seen.contains(k - node.val)) return true;Check if complement exists

seen.add(node.val);Add current node's value to set

return dfs(node.left, k) || dfs(node.right, k);Recurse left and right subtrees

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

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

bool dfs(TreeNode* node, int k, unordered_set<int>& seen) {
    if (!node) return false;
    if (seen.count(k - node->val)) return true;
    seen.insert(node->val);
    return dfs(node->left, k, seen) || dfs(node->right, k, seen);
}

bool findTarget(TreeNode* root, int k) {
    unordered_set<int> seen;
    return dfs(root, k, seen);
}

// 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

unordered_set<int>& seenPass hash set by reference to track visited values

if (!node) return false;Base case for recursion

if (seen.count(k - node->val)) return true;Check if complement exists in set

seen.insert(node->val);Add current node's value to set

return dfs(node->left, k, seen) || dfs(node->right, k, seen);Recurse left and right subtrees

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

function findTarget(root, k) {
    const seen = new Set();
    function dfs(node) {
        if (node === null) return false;
        if (seen.has(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
}

// 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

const seen = new Set();Initialize hash set to track visited values

function dfs(node) {Recursive DFS helper function

if (node === null) return false;Base case for recursion

if (seen.has(k - node.val)) return true;Check if complement exists in set

seen.add(node.val);Add current node's value to set

return dfs(node.left) || dfs(node.right);Recurse left and right subtrees

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once; hash set lookups are O(1) average.

💡 For n=20 nodes, this means about 20 operations, much faster than brute force.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews.

🧠

Inorder Traversal + Two Pointer

💡 This approach uses the BST's sorted property explicitly by converting it to a sorted array and then applying the classic two-pointer technique to find the target sum efficiently.

Intuition

Perform an inorder traversal to get a sorted list, then use two pointers at the start and end to find if any pair sums to k.

Algorithm

1. Perform an inorder traversal of the BST to get a sorted list of node values.
2. Initialize two pointers: left at start, right at end of the list.
3. While left < right, check sum of values at pointers.
4. If sum equals k, return true; if sum < k, move left pointer right; else move right pointer left.
5. If pointers cross without finding sum, return false.

💡 This approach is efficient and easy to implement once you understand inorder traversal and two-pointer technique.

</>

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)
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == k:
            return True
        elif s < k:
            left += 1
        else:
            right -= 1
    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:Helper to collect BST values in sorted order

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

left, right = 0, len(arr) - 1Initialize two pointers at array ends

while left < right:Loop until pointers cross

s = arr[left] + arr[right]Calculate sum of current pair

if s == k:Check if sum matches target

elif s < k:If sum too small, move left pointer right

else:If sum too large, move right pointer left

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 left = 0, right = arr.size() - 1;
        while (left < right) {
            int sum = arr.get(left) + arr.get(right);
            if (sum == k) return true;
            else if (sum < k) left++;
            else right--;
        }
        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

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

int left = 0, right = arr.size() - 1;Initialize two pointers at array ends

while (left < right) {Loop until pointers cross

int sum = arr.get(left) + arr.get(right);Calculate sum of current pair

if (sum == k) return true;Check if sum matches target

else if (sum < k) left++;If sum too small, move left pointer right

else right--;If sum too large, move right pointer left

#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 left = 0, right = (int)arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == k) return true;
        else if (sum < k) left++;
        else right--;
    }
    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

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

int left = 0, right = (int)arr.size() - 1;Initialize two pointers at array ends

while (left < right) {Loop until pointers cross

int sum = arr[left] + arr[right];Calculate sum of current pair

if (sum == k) return true;Check if sum matches target

else if (sum < k) left++;If sum too small, move left pointer right

else right--;If sum too large, move right pointer left

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);
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === k) return true;
        else if (sum < k) left++;
        else right--;
    }
    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

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

let left = 0, right = arr.length - 1;Initialize two pointers at array ends

while (left < right) {Loop until pointers cross

const sum = arr[left] + arr[right];Calculate sum of current pair

if (sum === k) return true;Check if sum matches target

else if (sum < k) left++;If sum too small, move left pointer right

else right--;If sum too large, move right pointer left

⏱

Complexity

TimeO(n)

SpaceO(n)

Inorder traversal takes O(n), two-pointer scan takes O(n).

💡 For n=20 nodes, about 40 operations total, very efficient.

Interview Verdict: Accepted

This approach is optimal in time and easy to implement, making it a great choice in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the hash set or two-pointer approach is preferred for efficiency and clarity. Brute force is useful only to demonstrate understanding.

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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by optimized solutions. Practice coding and testing each approach.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach and its inefficiency.Explain the hash set optimization and how it improves time complexity.Present the inorder traversal + two-pointer approach as an elegant solution leveraging BST properties.Code the chosen approach carefully and test with edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of BST traversal, ability to optimize naive solutions, and coding correctness. They also check if you handle edge cases and explain tradeoffs.

Common Follow-ups

• What if the BST is very large and you want to optimize space? → Use iterative inorder traversal with two stacks.
• Can you solve this without extra space? → Use BST iterators simulating two pointers without array.
• What if the tree is not a BST? → Use hash set approach only.
• How to handle duplicates? → Ensure pairs are distinct nodes.

💡 These follow-ups test deeper understanding of BST iterators, space optimization, and problem variations.

🔍

Pattern Recognition

When to Use

1) Problem involves BST and target sum; 2) Need to find two nodes summing to k; 3) BST property can be leveraged; 4) Efficient pair search required.

Signature Phrases

two elements in the BSTsum is equal to kreturn true if exists

NOT This Pattern When

Problems asking for path sums or subtree sums are different patterns.

Similar Problems

Two Sum - classic array version of the problem3Sum - extension to three elementsFind Target in BST - similar problem with different constraints

Practice

1. Given the following code for deleting a node in a BST, what is the value of root.val after calling deleteNode(root, 3) on the BST constructed by inserting nodes in order: 5, 3, 6?

easy

A. 6

B. 5

C. 3

D. null (root deleted)

Solution

1. Step 1: Construct BST and locate node 3

   BST: root=5, left=3, right=6. Node with value 3 is a leaf (no children).

2. Step 2: Delete node 3

   Since node 3 has no children, deletion returns null for root.left. Root remains 5 with left child null and right child 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Root value unchanged at 5 after deleting leaf 3 [OK]

Hint: Deleting leaf node returns null for that subtree [OK]

Common Mistakes:

• Confusing root with deleted node
• Replacing root value incorrectly
• Assuming root is deleted

2. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

3. You are given a binary search tree and a value range [low, high]. You need to remove all nodes whose values fall outside this range, ensuring the resulting tree remains a valid BST. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Iteratively prune the BST by adjusting pointers using BST properties without rebuilding the tree.

B. Apply dynamic programming to store subtrees and decide which to keep based on range constraints.

C. Use a greedy approach to remove nodes one by one by checking each node's value and deleting if out of range.

D. Perform an inorder traversal to collect all valid nodes, then rebuild the BST from the sorted list.

Solution

1. Step 1: Understand the problem constraints

   The problem requires trimming nodes outside [low, high] while preserving BST properties efficiently.

2. Step 2: Evaluate approaches

   Rebuilding the tree (A) wastes time and space. Greedy removal (C) is inefficient and may break BST structure. DP (B) is unnecessary and overcomplicates. Iterative pruning (D) leverages BST properties to skip subtrees and adjust pointers in O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterative pruning uses BST properties optimally [OK]

Hint: Use BST properties to prune iteratively for optimal trimming [OK]

Common Mistakes:

• Rebuilding tree wastes space and time
• Greedy removal breaks BST structure

4. You are given a binary tree and need to determine if it satisfies the property that for every node, all nodes in its left subtree have smaller values and all nodes in its right subtree have larger values, with no duplicates allowed. Which approach guarantees an optimal solution to this problem?

easy

A. Check each node by comparing it only with its immediate children recursively.

B. Apply a greedy algorithm that validates nodes as soon as they are visited.

C. Use dynamic programming to store subtree min and max values and combine results bottom-up.

D. Perform an inorder traversal and verify that the node values are strictly increasing.

Solution

1. Step 1: Understand BST property

   The BST property requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater, strictly increasing in inorder traversal.

2. Step 2: Recognize inorder traversal pattern

   Inorder traversal of a valid BST produces a strictly increasing sequence of values, so verifying this sequence guarantees correctness efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal yields sorted values for BST [OK]

Hint: Inorder traversal of BST is strictly increasing [OK]

Common Mistakes:

• Only comparing node with immediate children
• Using greedy checks without global ordering
• Confusing subtree min/max with inorder sequence

5. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time