BST Find Maximum Element in DSA Go

Mental Model

In a BST, the biggest number is always the rightmost node. Just keep going right until you can't go further.

Analogy: Imagine a line of people standing from shortest to tallest, left to right. The tallest person is at the far right end.

      10
     /  \
    5    15
          \
           20
            \
             25
↑root

Dry Run Walkthrough

Input: BST with nodes 10 -> 5, 15 -> 20 -> 25; find max element

Goal: Find the largest value in the BST by moving right until no more right child

Step 1: Start at root node 10

10 -> [curr->15] -> 20 -> 25
5 (left child of 10)

Why: We begin at the root to find the maximum

Step 2: Move curr pointer from 10 to right child 15

10 -> 15 -> [curr->20] -> 25
5 (left child of 10)

Why: Maximum is always in the right subtree, so move right

Step 3: Move curr pointer from 15 to right child 20

10 -> 15 -> 20 -> [curr->25]
5 (left child of 10)

Why: Keep moving right to find bigger values

Step 4: Move curr pointer from 20 to right child 25

10 -> 15 -> 20 -> 25 [curr]
5 (left child of 10)

Why: Continue moving right until no more right child

Step 5: No right child of 25, stop and return 25

10 -> 15 -> 20 -> 25 [curr]
5 (left child of 10)

Why: Rightmost node found, this is the maximum

Result:

10 -> 15 -> 20 -> 25 [max]
5 (left child of 10)
Maximum element is 25

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a BST node
type Node struct {
    val   int
    left  *Node
    right *Node
}

// Insert inserts a value into the BST
func (n *Node) Insert(val int) *Node {
    if n == nil {
        return &Node{val: val}
    }
    if val < n.val {
        n.left = n.left.Insert(val)
    } else {
        n.right = n.right.Insert(val)
    }
    return n
}

// FindMax finds the maximum value in the BST
func (n *Node) FindMax() int {
    curr := n
    for curr.right != nil {
        curr = curr.right // move right to find bigger values
    }
    return curr.val // rightmost node value is max
}

func main() {
    var root *Node
    values := []int{10, 5, 15, 20, 25}
    for _, v := range values {
        root = root.Insert(v)
    }
    maxVal := root.FindMax()
    fmt.Printf("Maximum element is %d\n", maxVal)
}

curr := n

start at root node

for curr.right != nil {

keep moving right while right child exists

curr = curr.right // move right to find bigger values

advance curr to right child to find max

return curr.val // rightmost node value is max

return value of rightmost node

Output

Maximum element is 25

Complexity Analysis

Time: O(h) because we only traverse down the right children where h is the tree height

Space: O(1) because we use only a pointer variable and no extra space

vs Alternative: Compared to scanning all nodes (O(n)), this is faster as it uses BST property to go directly right

Edge Cases

Empty tree (root is nil)

Function is not called or handled outside; no max to find

DSA Go

No explicit guard in FindMax; caller must check root != nil

Tree with single node

FindMax returns that node's value immediately

DSA Go

for curr.right != nil { ... } loop exits immediately

All nodes only on left side (no right children)

FindMax returns root value as no right child exists

DSA Go

for curr.right != nil { ... } loop exits immediately

When to Use This Pattern

When asked to find the largest element in a BST, look for the rightmost node by following right children until none remain.

Common Mistakes

Mistake: Trying to search both left and right subtrees for max instead of just going right
Fix: Use BST property and only move right until no right child

Mistake: Not handling empty tree and calling FindMax on nil
Fix: Check if root is nil before calling FindMax

Summary

Finds the largest value in a BST by moving right until no more right child.

Use when you need the maximum element quickly in a BST.

The maximum is always the rightmost node in a BST.

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