Two Sum in BST in DSA C++ - Time & Space Complexity

Time Complexity: Two Sum in BST

O(n)

Understanding Time Complexity

We want to know how the time needed to find two numbers that add up to a target grows as the tree gets bigger.

How does the search time change when the number of nodes in the BST increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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);
}
    

This code searches the BST to find if any two nodes sum to the target value k using a depth-first search and a set to track visited values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once in the tree using recursion.
• How many times: Each node is visited exactly one time.

How Execution Grows With Input

As the number of nodes grows, the function checks each node once, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 node visits
100	About 100 node visits
1000	About 1000 node visits

Pattern observation: The operations increase in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two sum grows directly with the number of nodes in the BST.

Common Mistake

[X] Wrong: "Because the tree is sorted, we can find the two sum in less than linear time like O(log n)."

[OK] Correct: The code visits every node to check pairs, so it still needs to look at all nodes in the worst case.

Interview Connect

Understanding how to analyze recursive tree searches helps you explain your approach clearly and shows you know how the algorithm scales with input size.

Self-Check

"What if we used an in-order traversal to create a sorted list first, then used two pointers to find the sum? How would the time complexity change?"