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.

Practice

1. What does the search operation in a Binary Search Tree (BST) do?

easy

A. Finds whether a given value exists in the BST

B. Deletes a node from the BST

C. Inserts a new node into the BST

D. Traverses all nodes in the BST

Solution

1. Step 1: Understand the purpose of BST search

   The search operation is designed to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds nodes, deletion removes nodes, and traversal visits nodes. Search only checks for existence.

3. Final Answer:

   Finds whether a given value exists in the BST -> Option A

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns the node always
• Assuming search traverses all nodes

2. Which of the following is the correct Go function signature for a BST search method that returns a boolean indicating if a value exists?

easy

A. func Search(val int) *Node

B. func (root *Node) Search(val int) bool

C. func (root Node) Search(val string) bool

D. func Search(root Node, val int) int

Solution

1. Step 1: Identify method receiver and return type

   BST search is usually a method on a pointer to Node and returns bool for found or not.

2. Step 2: Check parameter types and return type

   func (root *Node) Search(val int) bool uses pointer receiver, int parameter, and bool return which matches the expected signature.

3. Final Answer:

   func (root *Node) Search(val int) bool -> Option B

4. Quick Check:

   Pointer receiver + bool return = func (root *Node) Search(val int) bool [OK]

Hint: Search returns bool, uses pointer receiver for tree nodes [OK]

Common Mistakes:

• Using value receiver instead of pointer
• Wrong parameter or return types
• Confusing method vs function signatures

3. Given the BST below and the Go code snippet, what will be the output? BST structure: ``` 10 / \ 5 15 / 3 ``` Go code:

found := root.Search(3)
fmt.Println(found)

medium

A. true

B. false

C. nil

D. runtime error

Solution

1. Step 1: Trace the search for value 3 in the BST

   Starting at root 10, 3 < 10, go left to 5; 3 < 5, go left to 3; found node with value 3.

2. Step 2: Understand the returned value and print output

   Search returns true because 3 exists; printing true outputs 'true'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   3 found in BST = true [OK]

Hint: Follow BST left/right rules to find value [OK]

Common Mistakes:

• Assuming search returns node instead of bool
• Confusing true/false output
• Ignoring BST structure when tracing

4. The following Go code for BST search has a bug. What is the bug?

func (root *Node) Search(val int) bool {
    if root == nil {
        return false
    }
    if root.Value == val {
        return true
    }
    if val < root.Value {
        return root.Search(val)
    } else {
        return root.Search(val)
    }
}

medium

A. Base case for nil root is missing

B. Uses value receiver instead of pointer

C. Returns int instead of bool

D. Recursive calls do not move to left or right child nodes

Solution

1. Step 1: Analyze recursive calls in search method

   Both recursive calls use root.Search(val) without moving to root.Left or root.Right, causing infinite recursion.

2. Step 2: Identify correct recursive calls

   Should call root.Left.Search(val) if val < root.Value, else root.Right.Search(val) to move down the tree.

3. Final Answer:

   Recursive calls do not move to left or right child nodes -> Option D

4. Quick Check:

   Recursive calls must move down tree [OK]

Hint: Recursive calls must go to left or right child [OK]

Common Mistakes:

• Calling search on same node causing infinite loop
• Missing base case for nil
• Wrong return types

5. You want to search for a value in a BST but also count how many nodes you visited during the search. Which modification to the search function is best?

hard

A. Use a global variable to count nodes visited during search

B. Return the node instead of bool and count nodes outside the function

C. Add a counter parameter passed by pointer and increment it on each node visited

D. Modify the BST to store counts in each node

Solution

1. Step 1: Understand the need to count nodes during search

   Counting nodes visited requires tracking each node checked during recursion.

2. Step 2: Choose method to count nodes visited

   Passing a pointer to a counter variable and incrementing it at each node visit allows accurate counting without side effects.

3. Final Answer:

   Add a counter parameter passed by pointer and increment it on each node visited -> Option C

4. Quick Check:

   Pass counter pointer to track visits [OK]

Hint: Pass counter pointer to track nodes visited [OK]

Common Mistakes:

• Using global variables causing side effects
• Counting outside search missing recursive visits
• Changing BST structure unnecessarily