Two Sum in BST in DSA Typescript - 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 increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set();
  function dfs(node: TreeNode | null): boolean {
    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 by traversing all nodes once and checking complements in a set.

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 exactly once during the depth-first search.

How Execution Grows With Input

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

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

Pattern observation: The operations increase linearly as the tree size increases.

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 tree.

Common Mistake

[X] Wrong: "Because the tree is a BST, searching for pairs is faster than visiting all nodes."

[OK] Correct: The code visits every node once to check pairs, so it still takes time proportional to all nodes, not less.

Interview Connect

Understanding this helps you explain how traversing a tree and using extra space for quick lookups works together, a common pattern in coding problems.

Self-Check

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