BST Search Operation in DSA Go - Execution Trace

Concept Flow - BST Search Operation

Start at root

↓

Compare target with current node

↓

Equal?

Yes→Found node, stop

↓

Target < current?

Yes→Go left child

↓

Target > current?

Yes→Go right child

↓

If child is None

→Not found, stop

Start at the root node, compare the target value with current node's value, move left or right accordingly until found or no child exists.

Execution Sample

DSA Go

func BSTSearch(root *Node, target int) *Node {
  current := root
  for current != nil {
    if target == current.Value {
      return current
    } else if target < current.Value {
      current = current.Left
    } else {
      current = current.Right
    }
  }
  return nil
}

Searches for a target value in a BST by traversing left or right child nodes based on comparisons.

Execution Table

Step	Operation	Current Node Value	Comparison	Pointer Change	Visual State
1	Start at root	15	target=10 < 15	Move to left child	15 / \ 10 20 / 8 12
2	Compare with 10	10	target=10 == 10	Found node, stop	15 / \ 10 20 / 8 12
3	End	10	Found target	No change	15 / \ 10 20 / 8 12

💡 Target found at node with value 10, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
current	15 (root)	10 (left child)	10 (found)	10 (found)
target	10	10	10	10

Key Moments - 3 Insights

Why do we move left when target is less than current node?

Because in a BST, left child nodes hold smaller values. As shown in step 1 of execution_table, target 10 < 15 so we move left.

What happens if the target is not in the tree?

The search moves down left or right until it reaches a nil child pointer, then stops returning nil. This is not shown here but would be the exit condition if no match found.

Why do we stop when current node value equals target?

Because we found the node containing the target value, so no further traversal is needed. See step 2 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node value at step 1?

A 15

B 10

C 20

D 8

💡 Hint

Check the 'Current Node Value' column in row for step 1 in execution_table.

At which step does the search find the target node?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'Operation' and 'Comparison' columns in execution_table rows.

If target was 25 instead of 10, which pointer change would happen at step 1?

A Move to left child

B Move to right child

C Found node, stop

D No change

💡 Hint

Refer to the 'Comparison' and 'Pointer Change' columns in execution_table step 1.

Concept Snapshot

BST Search Operation:
- Start at root node
- Compare target with current node value
- If equal, found node
- If target < current, go left child
- If target > current, go right child
- Stop if child is nil (not found)

Full Transcript

This visual trace shows how to search a value in a Binary Search Tree (BST). We start at the root node and compare the target value with the current node's value. If they are equal, we found the node and stop. If the target is less, we move to the left child; if greater, to the right child. We repeat this until we find the target or reach a nil child pointer, meaning the target is not in the tree. The execution table tracks each step, showing the current node, comparison, pointer changes, and the tree's visual state. Variable tracker shows how the current pointer moves through the tree. Key moments clarify why we move left or right and when we stop. The quiz tests understanding of these steps.