Two Sum in BST in DSA Javascript - Time & Space Complexity

Time Complexity: Two Sum in BST

O(n)

Understanding Time Complexity

We want to know how long it takes to find two numbers in a BST that add up to a target.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code searches the BST to find if two values sum to k using a set to track seen values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive traversal of each node in the BST.
• How many times: Each node is visited once during the depth-first search.

How Execution Grows With Input

As the number of nodes grows, the function visits each node once.

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

Pattern observation: The work grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two sum grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because the tree is sorted, we can find the pair in less than linear time."

[OK] Correct: The code visits every node once to check pairs, so it still takes time proportional to the tree size.

Interview Connect

Understanding how traversal and lookups combine helps you explain your approach clearly and confidently.

Self-Check

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