Kth Smallest Element in a BST

🎯

Kth Smallest Element in a BST

mediumTREEAmazonGoogleFacebook

Imagine you have a sorted collection of numbers stored efficiently in a binary search tree, and you want to quickly find the kth smallest number without flattening the entire tree.

💡 This problem tests understanding of BST properties and tree traversal. Beginners often struggle because they try to flatten the tree fully or don't leverage the BST's sorted nature, leading to inefficient solutions.

📋

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

The number of nodes in the tree is n, where 1 ≤ n ≤ 10^51 ≤ k ≤ nNode values are unique integers

💡

Example

Input"root = [3,1,4,null,2], k = 1"

Output1

The in-order traversal of the BST is [1,2,3,4]. The 1st smallest element is 1.

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

Output3

In-order traversal: [1,2,3,4,5,6]. The 3rd smallest element is 3.

• k equals 1 (smallest element) → returns smallest node value
• k equals n (largest element) → returns largest node value
• Tree with only one node → returns that node's value regardless of k=1
• Skewed tree (all nodes only left or right) → traversal still works correctly

⚠️

Common Mistakes

Not stopping traversal early in recursive approach

Unnecessary traversal of entire tree, leading to timeouts on large inputs

✅ Add a condition to stop recursion once kth element is found

Using k as zero-based index instead of one-based

Returns wrong element or index out of range error

✅ Adjust indexing by subtracting 1 when accessing list or counting nodes

Not handling null nodes properly in recursion

Runtime errors or infinite recursion

✅ Add base case to return when node is null

Confusing inorder traversal order

Incorrect element returned because traversal order is wrong

✅ Remember inorder is left, root, right for BST to get sorted order

Using recursion without considering stack overflow on skewed trees

Stack overflow error on deep trees

✅ Use iterative approach with explicit stack to avoid recursion limits

🧠

Brute Force (Inorder Traversal with Full List)

💡 This approach exists to build intuition by fully traversing the BST and collecting all elements in sorted order, which is straightforward but not optimal for large trees.

Intuition

Perform an inorder traversal to get all node values in sorted order, then return the kth element from the list.

Algorithm

1. Traverse the BST inorder and store all node values in a list.
2. After traversal, the list is sorted because of BST properties.
3. Return the element at index k-1 from the list.

💡 The main challenge is understanding that inorder traversal of BST yields sorted order, making it easy to pick kth smallest after traversal.

</>

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 kthSmallest(root: Optional[TreeNode], k: int) -> int:
    def inorder(node: Optional[TreeNode], acc: List[int]):
        if not node:
            return
        inorder(node.left, acc)
        acc.append(node.val)
        inorder(node.right, acc)

    elements = []
    inorder(root, elements)
    return elements[k-1]

# Driver code to test
if __name__ == '__main__':
    # Construct BST: [3,1,4,null,2]
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

def inorder(node: Optional[TreeNode], acc: List[int]):Defines helper function to collect nodes inorder

if not node:Base case to stop recursion at leaf's child

inorder(node.left, acc)Traverse left subtree first to get smaller elements

acc.append(node.val)Add current node's value after left subtree to maintain sorted order

inorder(node.right, acc)Traverse right subtree for larger elements

elements = []Initialize list to store inorder traversal results

inorder(root, elements)Start traversal from root

return elements[k-1]Return kth smallest element from sorted list

import java.util.*;

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

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> elements = new ArrayList<>();
        inorder(root, elements);
        return elements.get(k - 1);
    }

    private void inorder(TreeNode node, List<Integer> acc) {
        if (node == null) return;
        inorder(node.left, acc);
        acc.add(node.val);
        inorder(node.right, acc);
    }

    // Driver code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

List<Integer> elements = new ArrayList<>();Create list to hold inorder traversal

inorder(root, elements);Start inorder traversal from root

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

acc.add(node.val);Add current node value after left subtree traversal

return elements.get(k - 1);Return kth smallest element from sorted list

public static void main(String[] args)Driver code to test the solution

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

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

class Solution {
public:
    void inorder(TreeNode* node, vector<int>& acc) {
        if (!node) return;
        inorder(node->left, acc);
        acc.push_back(node->val);
        inorder(node->right, acc);
    }

    int kthSmallest(TreeNode* root, int k) {
        vector<int> elements;
        inorder(root, elements);
        return elements[k - 1];
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

void inorder(TreeNode* node, vector<int>& acc)Helper function to collect nodes inorder

if (!node) return;Stop recursion at null nodes

inorder(node->left, acc);Traverse left subtree first

acc.push_back(node->val);Add current node value after left subtree

return elements[k - 1];Return kth smallest element from sorted vector

int main()Driver code to test the solution

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

function kthSmallest(root, k) {
    const elements = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        elements.push(node.val);
        inorder(node.right);
    }
    inorder(root);
    return elements[k - 1];
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

function inorder(node) {Helper function to traverse tree inorder

if (!node) return;Base case to stop recursion

inorder(node.left);Traverse left subtree first

elements.push(node.val);Add current node value after left subtree

return elements[k - 1];Return kth smallest element from sorted array

console.log(kthSmallest(root, 1));Test the function with example input

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit every node once during inorder traversal, and store all n nodes in a list.

💡 For n=20 nodes, this means about 20 operations to traverse and store, which is manageable but not efficient for very large trees.

Interview Verdict: Accepted but not optimal for large trees

This approach works but uses extra space and time; interviewers expect more efficient solutions.

🧠

Optimized Recursive Inorder with Early Stopping

💡 This approach improves on brute force by stopping traversal once the kth smallest element is found, saving unnecessary work.

Intuition

Perform inorder traversal but keep track of how many nodes have been visited; stop and return as soon as kth node is reached.

Algorithm

1. Initialize a counter to track number of nodes visited.
2. Traverse the BST inorder recursively.
3. Increment counter when visiting a node.
4. When counter equals k, record the node's value and stop traversal.
5. Return the recorded value.

💡 The key is to stop recursion early to avoid traversing the entire tree unnecessarily.

</>

Code

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:
    count = 0
    result = None

    def inorder(node: Optional[TreeNode]):
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)

    inorder(root)
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

count = 0Initialize counter for visited nodes

result = NoneStore kth smallest value once found

if not node or result is not None:Stop recursion if node is null or kth element found

count += 1Increment count when visiting a node

if count == k:Check if current node is kth smallest

result = node.valRecord kth smallest value

inorder(root)Start traversal from root

return resultReturn the found kth smallest element

import java.util.*;

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

public class Solution {
    private int count = 0;
    private int result = -1;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null || result != -1) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

private int count = 0;Counter for visited nodes

private int result = -1;Store kth smallest value once found

if (node == null || result != -1) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count == k)Check if current node is kth smallest

result = node.val;Record kth smallest value

inorder(root, k);Start traversal from root

return result;Return kth smallest element

#include <iostream>
using namespace std;

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

class Solution {
    int count = 0;
    int result = -1;
public:
    void inorder(TreeNode* node, int k) {
        if (!node || result != -1) return;
        inorder(node->left, k);
        count++;
        if (count == k) {
            result = node->val;
            return;
        }
        inorder(node->right, k);
    }

    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

int count = 0;Counter for nodes visited

int result = -1;Store kth smallest value once found

if (!node || result != -1) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count == k)Check if current node is kth smallest

result = node->val;Record kth smallest value

inorder(root, k);Start traversal from root

return result;Return kth smallest element

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

function kthSmallest(root, k) {
    let count = 0;
    let result = null;

    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        inorder(node.right);
    }

    inorder(root);
    return result;
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

let count = 0;Counter for visited nodes

let result = null;Store kth smallest value once found

if (!node || result !== null) return;Stop recursion if node null or kth found

count++;Increment count when visiting node

if (count === k)Check if current node is kth smallest

result = node.val;Record kth smallest value

inorder(root);Start traversal from root

return result;Return kth smallest element

⏱

Complexity

TimeO(H + k)

SpaceO(H)

In the best case, we only traverse down to kth node, where H is tree height. Space is recursion stack height.

💡 For balanced trees with height ~log n, and k=10, this means about 10-15 operations, much faster than full traversal.

Interview Verdict: Accepted and efficient for balanced trees

This approach is a good balance of simplicity and efficiency, often preferred in interviews.

🧠

Iterative Inorder Traversal Using Stack

💡 This approach uses an explicit stack to simulate recursion, which is often preferred in interviews to avoid recursion overhead and stack overflow.

Intuition

Use a stack to traverse the BST inorder iteratively, popping nodes and counting until kth smallest is found.

Algorithm

1. Initialize an empty stack and set current node to root.
2. While current is not null or stack is not empty:
3. Push all left children of current onto stack.
4. Pop from stack, increment count.
5. If count equals k, return popped node's value.
6. Move to right child of popped node.

💡 The stack keeps track of nodes to visit next, simulating recursion but with explicit control.

</>

Code

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

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

Line Notes

stack = []Initialize stack to simulate recursion

while current or stack:Continue while nodes remain to visit

while current:Go as left as possible pushing nodes

stack.append(current)Push current node to stack before going left

current = stack.pop()Pop node to visit in inorder sequence

count += 1Increment count for visited node

if count == k:Check if kth smallest found

current = current.rightMove to right subtree after visiting node

import java.util.*;

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

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        int count = 0;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            count++;
            if (count == k) return current.val;
            current = current.right;
        }
        return -1; // Should never reach here if k valid
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.kthSmallest(root, 1)); // Output: 1
    }
}

Line Notes

Stack<TreeNode> stack = new Stack<>();Stack to simulate recursion

while (current != null || !stack.isEmpty()) {Traverse while nodes remain

stack.push(current);Push current node before going left

current = stack.pop();Pop node to visit in inorder

count++;Increment count for visited node

if (count == k) return current.val;Return kth smallest when found

current = current.right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

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

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stk;
        TreeNode* current = root;
        int count = 0;

        while (current || !stk.empty()) {
            while (current) {
                stk.push(current);
                current = current->left;
            }
            current = stk.top();
            stk.pop();
            count++;
            if (count == k) return current->val;
            current = current->right;
        }
        return -1; // Should not happen
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl; // Output: 1
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to simulate recursion

while (current || !stk.empty()) {Traverse while nodes remain

stk.push(current);Push current node before going left

current = stk.top();Pop node to visit in inorder

count++;Increment count for visited node

if (count == k) return current->val;Return kth smallest when found

current = current->right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

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

function kthSmallest(root, k) {
    const stack = [];
    let current = root;
    let count = 0;

    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        count++;
        if (count === k) return current.val;
        current = current.right;
    }
    return -1; // Should not happen
}

// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
console.log(kthSmallest(root, 1)); // Output: 1

Line Notes

const stack = [];Stack to simulate recursion

while (current !== null || stack.length > 0) {Traverse while nodes remain

stack.push(current);Push current node before going left

current = stack.pop();Pop node to visit in inorder

count++;Increment count for visited node

if (count === k) return current.val;Return kth smallest when found

current = current.right;Move to right subtree after visiting node

return -1;Fallback return, should not happen if k valid

⏱

Complexity

TimeO(H + k)

SpaceO(H)

Stack stores nodes along path; we visit nodes until kth smallest found. H is tree height.

💡 For balanced trees, this is efficient and avoids recursion stack overhead.

Interview Verdict: Accepted and preferred iterative solution

Interviewers often prefer iterative solutions to test understanding of traversal mechanics.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, approach 2 or 3 is best: efficient and easy to implement. Approach 1 is good to mention but not code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	Yes (due to recursion depth)	Yes	Mention only - never code
2. Optimized Recursive Inorder with Early Stopping	O(H + k)	O(H)	Yes (for very deep trees)	Yes	Good to code if recursion allowed
3. Iterative Inorder Traversal Using Stack	O(H + k)	O(H)	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize step-by-step, and finally code the best approach.

How to Present

Clarify input format and constraints.State the brute force approach: full inorder traversal and indexing.Explain inefficiency and propose early stopping recursion.Discuss iterative stack-based traversal as an alternative.Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of BST properties, inorder traversal, recursion vs iteration, and optimization skills.

Common Follow-ups

• What if the BST is modified frequently? → Use augmented BST with node counts.
• How to find kth largest element? → Reverse inorder traversal.

💡 These follow-ups test your ability to adapt the solution to variations and optimize for dynamic data.

🔍

Pattern Recognition

When to Use

1) Input is a BST, 2) Need kth smallest/largest element, 3) Sorted order required, 4) Traversal or counting needed

Signature Phrases

kth smallest elementbinary search treeinorder traversal

NOT This Pattern When

Problems asking for path sums or subtree properties without order requirements

Similar Problems

Kth Largest Element in a BST - same pattern but reversed traversalClosest Binary Search Tree Value - uses BST traversal to find closest value

Practice

1. You need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. You are given a sorted array of unique integers and need to construct a binary search tree with minimal height. Which approach guarantees the resulting tree is height-balanced and constructed in O(n) time?

easy

A. Use a divide-and-conquer recursion that picks the middle element as root and recursively builds left and right subtrees.

B. Insert elements one by one into an empty BST using standard BST insertion.

C. Use a greedy approach that always inserts the smallest remaining element as the left child.

D. Build a balanced BST by repeatedly merging two smaller balanced BSTs.

Solution

1. Step 1: Understand the problem constraints

   The input is a sorted array, and the goal is to build a height-balanced BST efficiently.

2. Step 2: Evaluate approaches

   Inserting elements one by one leads to skewed trees and O(n^2) time. Greedy insertion of smallest elements does not guarantee balance. Merging BSTs is not straightforward and inefficient. The divide-and-conquer approach picks the middle element as root, ensuring balanced subtrees and O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Middle element chosen recursively -> balanced BST in O(n) time [OK]

Hint: Middle element recursion ensures balanced BST [OK]

Common Mistakes:

• Thinking inserting one by one is efficient
• Assuming greedy insertion balances tree

3. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

4. What is the worst-case time complexity of the optimized recursive BST node deletion algorithm that uses the in-order successor to replace a node with two children?

medium

A. O(h) where h is the height of the BST

B. O(h^2) due to recursive calls and successor search

C. O(log n) always, since BST is balanced

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

Solution

1. Step 1: Identify height-based operations

   Deletion involves searching down the tree (O(h)) and finding the in-order successor, which is also O(h) in worst case.

2. Step 2: Combine operations and recursion

   Successor search and recursive deletion happen along a path of length h, so total time is O(h), not O(h^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time proportional to tree height, not total nodes or squared height [OK]

Hint: Deletion time depends on tree height, not total nodes [OK]

Common Mistakes:

• Assuming balanced BST always (log n)
• Confusing recursion depth with squared complexity
• Thinking successor search adds extra factor

5. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early