BST Inorder Successor in DSA Go - Build from Scratch

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the next bigger number after a given number in the tree. This is called the inorder successor.Think of the BST as a sorted list of numbers arranged in a tree shape. Finding the inorder successor means finding the number that comes right after a given number when you look at the numbers in order.

🎯 Goal: Build a program in Go that creates a BST, sets a target node value, finds the inorder successor of that node, and prints the result.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 9, 25, 5, 12, 11, 14

Set a variable called target to the node with value 9

Write a function inorderSuccessor that finds the inorder successor of the target node in the BST

Print the value of the inorder successor node or nil if none exists

💡 Why This Matters

🌍 Real World

Finding the inorder successor in a BST is useful in database indexing, where you want to find the next record in sorted order efficiently.

💼 Career

Understanding BST operations like inorder successor is important for software engineers working with search algorithms, data indexing, and optimization.

1

Create the BST nodes

Create the BST nodes with values 20, 9, 25, 5, 12, 11, and 14 using the TreeNode struct. Connect them to form the BST exactly as follows: 20 is root, 9 is left child of 20, 25 is right child of 20, 5 is left child of 9, 12 is right child of 9, 11 is left child of 12, and 14 is right child of 12.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    // Create BST nodes and connect them
    // Your code here
}

Hint

Use &TreeNode{Val: value} to create nodes and assign them to the correct Left or Right fields.

2

Set the target node

Create a variable called target and set it to point to the node with value 9 in the BST.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{Val: 20}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 25}
    root.Left.Left = &TreeNode{Val: 5}
    root.Left.Right = &TreeNode{Val: 12}
    root.Left.Right.Left = &TreeNode{Val: 11}
    root.Left.Right.Right = &TreeNode{Val: 14}

    // Set target node to root.Left
    // Your code here
}

Hint

The node with value 9 is the left child of the root node.

3

Write the inorderSuccessor function

Write a function called inorderSuccessor that takes root and target nodes as input and returns the inorder successor node of target in the BST. Use the BST property to find the successor efficiently.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderSuccessor(root *TreeNode, target *TreeNode) *TreeNode {
    // Your code here
}

func main() {
    root := &TreeNode{Val: 20}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 25}
    root.Left.Left = &TreeNode{Val: 5}
    root.Left.Right = &TreeNode{Val: 12}
    root.Left.Right.Left = &TreeNode{Val: 11}
    root.Left.Right.Right = &TreeNode{Val: 14}

    target := root.Left
}

Hint

Use a loop starting from root. If target.Val is less than current.Val, update successor and go left. Otherwise, go right. Return successor at the end.

4

Print the inorder successor value

Call the inorderSuccessor function with root and target. Print the value of the returned node if it is not nil. Otherwise, print nil.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderSuccessor(root *TreeNode, target *TreeNode) *TreeNode {
    var successor *TreeNode
    current := root
    for current != nil {
        if target.Val < current.Val {
            successor = current
            current = current.Left
        } else {
            current = current.Right
        }
    }
    return successor
}

func main() {
    root := &TreeNode{Val: 20}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 25}
    root.Left.Left = &TreeNode{Val: 5}
    root.Left.Right = &TreeNode{Val: 12}
    root.Left.Right.Left = &TreeNode{Val: 11}
    root.Left.Right.Right = &TreeNode{Val: 14}

    target := root.Left

    // Print the inorder successor value or nil
    // Your code here
}

Hint

Call inorderSuccessor(root, target). If the result is not nil, print its Val. Otherwise, print nil.