Two Sum in BST in DSA Go - 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.

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    var dfs func(node *TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return false
        }
        if seen[k - node.Val] {
            return true
        }
        seen[node.Val] = true
        return dfs(node.Left) || dfs(node.Right)
    }
    return dfs(root)
}
    

This code searches the BST to find if there are two nodes whose values add up to k using a depth-first search and a map 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 DFS.

How Execution Grows With Input

As the number of nodes (n) grows, the function visits each node once, so the operations grow roughly in direct proportion to n.

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

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 linearly with the number of nodes in the BST.

Common Mistake

[X] Wrong: "Because the tree is a BST, searching for pairs is O(log n)."

[OK] Correct: The code visits every node once to check pairs, so it must look at all nodes, making it linear, not logarithmic.

Interview Connect

Understanding this linear time complexity helps you explain how tree traversal and hash maps work together to solve problems efficiently.

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?"