BST Find Maximum Element in DSA Go - Execution Trace

Concept Flow - BST Find Maximum Element

Start at root node

↓

Check if right child exists?

No→Current node is max

Yes↓

Move to right child

↩Back to check right child

Start at the root and keep moving to the right child until there is no right child left. The last node visited is the maximum.

Execution Sample

DSA Go

func FindMax(root *Node) *Node {
    current := root
    for current != nil && current.Right != nil {
        current = current.Right
    }
    return current
}

This code finds the maximum element in a BST by moving right until no right child exists.

Execution Table

Step	Operation	Current Node Value	Right Child Exists?	Pointer Changes	Visual State
1	Start at root	15	Yes	current = root (15)	15 / \ 10 20 / \ 17 25
2	Move right	20	Yes	current = current.Right (20)	15 / \ 10 20 / \ 17 25
3	Move right	25	No	current = current.Right (25)	15 / \ 10 20 / \ 17 25
4	Return current	25	No	Return node with value 25	Max element found: 25

💡 No right child at node 25, so 25 is the maximum element.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	root (15)	15	20	25	25

Key Moments - 3 Insights

Why do we keep moving to the right child to find the maximum?

In a BST, all values to the right are greater. The execution_table rows 1 to 3 show moving right until no right child exists, which means the current node is the largest.

What if the tree has only one node?

If the root has no right child (execution_table step 1 shows 'Right Child Exists?' as No), the root itself is the maximum.

Why do we stop when current.Right is nil, not when current is nil?

Stopping at current.Right == nil means current is the last node on the right path. If we moved to current == nil, we would lose the reference to the max node. See execution_table step 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 2?

A 25

B 20

C 15

D 17

💡 Hint

Check the 'Current Node Value' column at step 2 in execution_table.

At which step does the algorithm stop moving right?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the step where 'Right Child Exists?' is No in execution_table.

If the root node had no right child, what would be the maximum element?

A The root node value

B The left child value

C Nil (no max)

D The right child value

💡 Hint

Refer to key_moments about single node tree and execution_table step 1.

Concept Snapshot

BST Find Maximum Element:
- Start at root node
- While right child exists, move right
- When no right child, current node is max
- Return current node
- Works because BST right subtree has larger values

Full Transcript

To find the maximum element in a Binary Search Tree (BST), start at the root node. Check if the current node has a right child. If yes, move to the right child and repeat. Continue this until the current node has no right child. This last node is the maximum element. This works because in a BST, all values in the right subtree are greater than the current node. The provided code uses a loop to move right until no right child exists, then returns the current node as the maximum. The execution table shows each step with the current node value and pointer changes. Key moments clarify why we move right and when to stop. The visual quiz tests understanding of the steps and conditions.

Practice

1. In a Binary Search Tree (BST), where is the maximum element always located?

easy

A. At any leaf node

B. At the rightmost node

C. At the root node

D. At the leftmost node

Solution

1. Step 1: Understand BST property

   In a BST, all nodes to the right of a node have greater values.

2. Step 2: Locate maximum element

   The maximum element is found by moving to the rightmost node, as it has no greater right child.

3. Final Answer:

   At the rightmost node -> Option B

4. Quick Check:

   Maximum = rightmost node [OK]

Hint: Maximum is always the rightmost node in BST [OK]

Common Mistakes:

• Confusing maximum with root node
• Thinking maximum is at leftmost node
• Assuming maximum can be any leaf

2. Which of the following Go code snippets correctly finds the maximum element in a BST node structure?

easy

A. for current.Left != nil { current = current.Left } return current.Value

B. return root.Value

C. for current.Right != nil { current = current.Right } return current.Value

D. for current != nil { current = current.Left } return current.Value

Solution

1. Step 1: Check loop condition for maximum

   Maximum is found by moving right until no right child exists.

2. Step 2: Verify code correctness

   for current.Right != nil { current = current.Right } return current.Value correctly loops while current.Right is not nil, then returns current.Value.

3. Final Answer:

   for current.Right != nil { current = current.Right } return current.Value -> Option C

4. Quick Check:

   Loop right child until nil = max [OK]

Hint: Loop right child until nil to find max [OK]

Common Mistakes:

• Looping left child instead of right
• Returning root value without traversal
• Loop condition incorrect or infinite

3. What will be the output of the following Go code snippet that finds the maximum element in a BST?

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func findMax(root *Node) int {
    current := root
    for current.Right != nil {
        current = current.Right
    }
    return current.Value
}

root := &Node{Value: 10}
root.Left = &Node{Value: 5}
root.Right = &Node{Value: 15}
root.Right.Right = &Node{Value: 20}

fmt.Println(findMax(root))

medium

A. 20

B. 15

C. 10

D. 5

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 15, right-right child 20 (rightmost node).

2. Step 2: Follow findMax function

   Function moves right until current.Right is nil, stopping at node with value 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Rightmost node value is maximum [OK]

Common Mistakes:

• Returning root value instead of rightmost
• Stopping at first right child
• Confusing left and right pointers

4. The following Go function is intended to find the maximum element in a BST but contains a bug. What is the bug?

func findMax(root *Node) int {
    current := root
    for current.Left != nil {
        current = current.Left
    }
    return current.Value
}

medium

A. All of the above

B. It does not handle empty tree (nil root)

C. It returns the minimum element instead of maximum

D. It incorrectly traverses left children instead of right

Solution

1. Step 1: Analyze traversal direction

   The code loops while current.Left != nil, moving left, which finds minimum, not maximum.

2. Step 2: Check for other issues

   Function does not check if root is nil, which can cause runtime error.

3. Final Answer:

   It incorrectly traverses left children instead of right; does not handle nil root; returns minimum instead of maximum -> Option A

4. Quick Check:

   Left traversal + no nil check = bugs [OK]

Hint: Traverse right, check nil root to avoid bugs [OK]

Common Mistakes:

• Using left instead of right pointer
• Ignoring nil root check
• Assuming code finds maximum correctly

5. Given a BST where some nodes have duplicate values, how would you modify the Go function to find the maximum element considering duplicates are allowed on the right subtree? Choose the best approach.

hard

A. Traverse left while current.Left != nil and current.Left.Value > current.Value

B. Return root.Value directly since duplicates are on right

C. Traverse right while current.Right != nil and current.Right.Value > current.Value

D. Traverse right while current.Right != nil only

Solution

1. Step 1: Understand duplicates in BST

   In a BST allowing duplicates on right, right subtree values are >= current value.

2. Step 2: Best traversal for maximum

   Traverse right while current.Right != nil only. Value checks like in C (>) stop early on equal duplicates before larger values (e.g., 10->10->12).

3. Final Answer:

   Traverse right while current.Right != nil only -> Option D

4. Quick Check:

   Structural rightmost traversal = max even with duplicates [OK]

Hint: Traverse right until nil regardless of duplicates [OK]

Common Mistakes:

• Using strict > comparison, stopping early on equals
• Traversing left instead of right
• Returning root value without traversal