BST Inorder Predecessor in DSA Go - Build from Scratch

Find Inorder Predecessor in a BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores unique integer values. You want to find the inorder predecessor of a given node value. The inorder predecessor of a node is the node with the largest value smaller than the given node's value.This is useful in scenarios like navigating a sorted list of items, or undoing steps in an ordered sequence.

🎯 Goal: Build a Go program that creates a BST, sets a target node value, finds the inorder predecessor of that node, and prints the predecessor's value or a message if none exists.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 10, 30, 5, 15, 25, 35

Set a target node value to 20

Implement a function to find the inorder predecessor of the target node in the BST

Print the predecessor's value or 'No predecessor' if it does not exist

💡 Why This Matters

🌍 Real World

Finding inorder predecessors is useful in databases and file systems where ordered data navigation is needed.

💼 Career

Understanding BST operations like inorder predecessor is important for software engineering roles involving data structures and algorithms.

1

Create the BST structure and insert nodes

Define a struct called Node with value int, left *Node, and right *Node. Then create a function insert(root *Node, val int) *Node that inserts a value into the BST. Finally, create a BST by inserting these values in order: 20, 10, 30, 5, 15, 25, 35. Store the root in a variable called root.

DSA Go

// Define Node struct and insert function
// Insert nodes 20, 10, 30, 5, 15, 25, 35 into BST
// Your code here

Hint

Use recursion in insert to place smaller values to the left and larger to the right.

2

Set the target node value

Create an integer variable called target and set it to 20.

DSA Go

package main

import "fmt"

// Set target node value
// Your code here

Hint

Just create a variable target and assign 20.

3

Implement function to find inorder predecessor

Write a function inorderPredecessor(root *Node, target int) *Node that finds the inorder predecessor of the node with value target in the BST rooted at root. Use the BST property and traversal logic to find the predecessor. The function should return a pointer to the predecessor node or nil if none exists. Call this function in main and store the result in a variable called pred.

DSA Go

package main

import "fmt"

// Write inorderPredecessor function here
// Call inorderPredecessor in main and assign to pred
// Your code here

Hint

Use a loop to traverse the tree. Move left if target is less or equal to current node's value, else update predecessor and move right.

4

Print the inorder predecessor result

In main, print the value of pred if it is not nil. Otherwise, print No predecessor. Use fmt.Println.

DSA Go

package main

import "fmt"

// Print predecessor value or 'No predecessor'
// Your code here

Hint

Check if pred is nil. If not, print pred.value. Otherwise, print No predecessor.