BST Find Maximum Element in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the maximum element in a BST

What is the output of the following Go code that finds the maximum element in a binary search tree?

DSA Go

package main
import "fmt"
type Node struct {
    value int
    left, right *Node
}
func findMax(root *Node) int {
    current := root
    for current.right != nil {
        current = current.right
    }
    return current.value
}
func main() {
    root := &Node{value: 10}
    root.left = &Node{value: 5}
    root.right = &Node{value: 20}
    root.right.left = &Node{value: 15}
    root.right.right = &Node{value: 25}
    fmt.Println(findMax(root))
}

A 15

B 20

C 25

D 10

💡 Hint

In a BST, the maximum value is found by going as far right as possible.

The function findMax traverses the tree by moving to the right child until it reaches the rightmost node, which holds the maximum value 25.

❓ Predict Output

intermediate

Output of findMax with single node BST

What will be printed when findMax is called on a BST with only one node?

DSA Go

package main
import "fmt"
type Node struct {
    value int
    left, right *Node
}
func findMax(root *Node) int {
    current := root
    for current.right != nil {
        current = current.right
    }
    return current.value
}
func main() {
    root := &Node{value: 42}
    fmt.Println(findMax(root))
}

A 42

B 0

C nil

D runtime error

💡 Hint

If there is only one node, that node is the maximum.

Since the root has no right child, the loop does not run and the root's value 42 is returned.

🔧 Debug

advanced

Identify the error in findMax function

What error will the following Go code produce when findMax is called with a nil root?

DSA Go

package main
import "fmt"
type Node struct {
    value int
    left, right *Node
}
func findMax(root *Node) int {
    current := root
    for current.right != nil {
        current = current.right
    }
    return current.value
}
func main() {
    var root *Node = nil
    fmt.Println(findMax(root))
}

A compilation error: missing return statement

B runtime error: invalid memory address or nil pointer dereference

C 0

D prints nothing

💡 Hint

Accessing fields of a nil pointer causes a runtime panic in Go.

The function tries to access current.right when current is nil, causing a nil pointer dereference runtime error.

🧠 Conceptual

advanced

Why does findMax traverse right children in a BST?

In a binary search tree, why does the findMax function move only to the right child nodes to find the maximum element?

A Because left children always have the maximum values

B Because the tree is balanced and right nodes are visited first

C Because the root node always contains the maximum value

D Because in a BST, all right children have values greater than their parent nodes

💡 Hint

Recall the BST property about left and right children values.

In a BST, left children have smaller values and right children have larger values than their parent nodes, so the maximum is found by going right.

🚀 Application

expert

Find maximum in BST after insertion

Given the following BST and the insertion of a new node with value 30, what will be the maximum element after insertion?

DSA Go

package main
import "fmt"
type Node struct {
    value int
    left, right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{value: val}
    }
    if val < root.value {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func findMax(root *Node) int {
    current := root
    for current.right != nil {
        current = current.right
    }
    return current.value
}
func main() {
    root := &Node{value: 10}
    root = insert(root, 5)
    root = insert(root, 20)
    root = insert(root, 25)
    root = insert(root, 15)
    root = insert(root, 30)
    fmt.Println(findMax(root))
}

A 30

B 25

C 15

D 20

💡 Hint

After inserting 30, it becomes the rightmost node.

The new node with value 30 is inserted as the right child of 25, making 30 the maximum element.

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