BST Find Maximum Element in DSA Go - Build from Scratch

BST Find Maximum Element

📖 Scenario: You are working with a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to find the contact with the highest phone number.

🎯 Goal: Build a Go program that creates a BST with given phone numbers, then finds and prints the maximum phone number stored in the BST.

📋 What You'll Learn

Create a BST node structure with an integer phone number

Insert given phone numbers into the BST

Write a function to find the maximum phone number in the BST

Print the maximum phone number found

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases often use BSTs to store and quickly find data like phone numbers.

💼 Career

Understanding BSTs and how to find maximum or minimum values is important for software engineers working on efficient data storage and retrieval.

1

Create BST Node Structure and Insert Function

Create a struct called Node with an integer field phoneNumber and two pointers left and right to Node. Then write a function insert(root *Node, phoneNumber int) *Node that inserts a phone number into the BST and returns the root node.

DSA Go

package main

// Your code here

Hint

Think of Node as a contact with a phone number and links to smaller and larger numbers.

2

Insert Given Phone Numbers into BST

Create a variable root of type *Node and insert these phone numbers into the BST in this order: 5551234, 5555678, 5550000, 5559999, 5554321.

DSA Go

package main

type Node struct {
    phoneNumber int
    left, right *Node
}

func insert(root *Node, phoneNumber int) *Node {
    if root == nil {
        return &Node{phoneNumber: phoneNumber}
    }
    if phoneNumber < root.phoneNumber {
        root.left = insert(root.left, phoneNumber)
    } else {
        root.right = insert(root.right, phoneNumber)
    }
    return root
}

func main() {
    var root *Node
    // Insert phone numbers into BST below
    // Your code here
}

Hint

Use the insert function to add each phone number to the BST.

3

Write Function to Find Maximum Phone Number

Write a function findMax(root *Node) int that returns the maximum phone number in the BST by following the right child nodes until none remain.

DSA Go

package main

type Node struct {
    phoneNumber int
    left, right *Node
}

func insert(root *Node, phoneNumber int) *Node {
    if root == nil {
        return &Node{phoneNumber: phoneNumber}
    }
    if phoneNumber < root.phoneNumber {
        root.left = insert(root.left, phoneNumber)
    } else {
        root.right = insert(root.right, phoneNumber)
    }
    return root
}

func main() {
    var root *Node
    root = insert(root, 5551234)
    root = insert(root, 5555678)
    root = insert(root, 5550000)
    root = insert(root, 5559999)
    root = insert(root, 5554321)
}

// Write findMax function below
// Your code here

Hint

Keep moving to the right child until there is no right child left, then return that node's phone number.

4

Print the Maximum Phone Number

In the main function, call findMax(root) and print the returned maximum phone number using fmt.Println. Import the fmt package at the top.

DSA Go

package main

import "fmt"

type Node struct {
    phoneNumber int
    left, right *Node
}

func insert(root *Node, phoneNumber int) *Node {
    if root == nil {
        return &Node{phoneNumber: phoneNumber}
    }
    if phoneNumber < root.phoneNumber {
        root.left = insert(root.left, phoneNumber)
    } else {
        root.right = insert(root.right, phoneNumber)
    }
    return root
}

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

func main() {
    var root *Node
    root = insert(root, 5551234)
    root = insert(root, 5555678)
    root = insert(root, 5550000)
    root = insert(root, 5559999)
    root = insert(root, 5554321)
    // Print the maximum phone number below
    // Your code here
}

Hint

Use fmt.Println(findMax(root)) or assign to a variable then print it.