BST Search Operation in DSA Go - Time & Space Complexity

Time Complexity: BST Search Operation

O(h)

Understanding Time Complexity

We want to understand how long it takes to find a value in a Binary Search Tree (BST).

How does the search time change as the tree grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func SearchBST(root *TreeNode, val int) *TreeNode {
    if root == nil || root.Val == val {
        return root
    }
    if val < root.Val {
        return SearchBST(root.Left, val)
    }
    return SearchBST(root.Right, val)
}
    

This code searches for a value in a BST by moving left or right depending on comparisons.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down one level of the tree.
• How many times: At most once per tree level until the value is found or a leaf is reached.

How Execution Grows With Input

Each step moves down one level, so the number of steps depends on the tree's height.

Input Size (n)	Approx. Operations (steps)
10 nodes	About 4 steps (if balanced)
100 nodes	About 7 steps (if balanced)
1000 nodes	About 10 steps (if balanced)

Pattern observation: In a balanced tree, steps grow slowly (logarithmically) as nodes increase.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the search time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Searching a BST always takes O(n) time because you might check every node."

[OK] Correct: In a balanced BST, you skip half the nodes each step, so search is much faster, about O(log n). Only in a very unbalanced tree does it become O(n).

Interview Connect

Understanding BST search time helps you explain how data structures speed up finding information, a key skill in coding interviews.

Self-Check

"What if the BST is completely unbalanced and looks like a linked list? How would the time complexity change?"