BST Inorder Predecessor in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Predecessor Function in BST

What is the output of the following Go code that finds the inorder predecessor of a node with value 15 in a BST?

DSA Go

package main

import "fmt"

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

func inorderPredecessor(root *Node, key int) *Node {
    var predecessor *Node
    current := root
    for current != nil {
        if key <= current.Val {
            current = current.Left
        } else {
            predecessor = current
            current = current.Right
        }
    }
    return predecessor
}

func main() {
    root := &Node{20, nil, nil}
    root.Left = &Node{10, nil, nil}
    root.Right = &Node{30, nil, nil}
    root.Left.Left = &Node{5, nil, nil}
    root.Left.Right = &Node{15, nil, nil}

    pred := inorderPredecessor(root, 15)
    if pred != nil {
        fmt.Println(pred.Val)
    } else {
        fmt.Println("nil")
    }
}

A 5

B 10

C 15

D nil

💡 Hint

Think about the largest value smaller than the key in the BST.

The inorder predecessor of 15 is the largest node smaller than 15. In this BST, 10 is the largest value less than 15.

🧠 Conceptual

intermediate

Understanding Inorder Predecessor in BST

In a Binary Search Tree (BST), what does the inorder predecessor of a node represent?

A The node with the smallest value greater than the given node

B The left child of the given node

C The node with the largest value smaller than the given node

D The right child of the given node

💡 Hint

Inorder traversal visits nodes in ascending order.

Inorder predecessor is the node visited just before the given node in inorder traversal, which means it has the largest value smaller than the given node.

🔧 Debug

advanced

Identify the Error in Inorder Predecessor Code

What error will the following Go code produce when trying to find the inorder predecessor of 10 in the BST?

DSA Go

package main

import "fmt"

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

func inorderPredecessor(root *Node, key int) *Node {
    var predecessor *Node
    current := root
    for current != nil {
        if key < current.Val {
            current = current.Left
        } else if key > current.Val {
            predecessor = current
            current = current.Right
        } else {
            if current.Left != nil {
                temp := current.Left
                for temp.Right != nil {
                    temp = temp.Right
                }
                predecessor = temp
            }
            break
        }
    }
    return predecessor
}

func main() {
    root := &Node{20, nil, nil}
    root.Left = &Node{10, nil, nil}
    root.Right = &Node{30, nil, nil}
    root.Left.Left = &Node{5, nil, nil}
    root.Left.Right = &Node{15, nil, nil}

    pred := inorderPredecessor(root, 10)
    if pred != nil {
        fmt.Println(pred.Val)
    } else {
        fmt.Println("nil")
    }
}

A It causes a runtime panic

B It prints 15

C It prints nil

D It prints 5

💡 Hint

Check how the predecessor is found when the node has a left subtree.

The code correctly finds the inorder predecessor by going to the left subtree and then rightmost node. For 10, predecessor is 5.

📝 Syntax

advanced

Identify Syntax Error in BST Inorder Predecessor Code

Which option contains a syntax error in the Go code for finding the inorder predecessor in a BST?

DSA Go

func inorderPredecessor(root *Node, key int) *Node {
    var predecessor *Node
    current := root
    for current != nil {
        if key <= current.Val {
            current = current.Left
        } else {
            predecessor = current
            current = current.Right
        }
    }
    return predecessor
}

A func inorderPredecessor(root *Node, key int) *Node { var predecessor *Node current := root for current != nil { if key <= current.Val { current = current.Left else { predecessor = current current = current.Right } } } return predecessor }

B } rossecederp nruter } } thgiR.tnerruc = tnerruc tnerruc = rossecederp { esle } tfeL.tnerruc = tnerruc { laV.tnerruc =< yek fi { lin =! tnerruc rof toor =: tnerruc edoN* rossecederp rav { edoN* )tni yek ,edoN* toor(rossecederPredroni cnuf

C func inorderPredecessor(root *Node, key int) *Node { var predecessor *Node current := root for current != nil { if key <= current.Val { current = current.Left } else { predecessor = current current = current.Right } } return predecessor }

D unc inorderPredecessor(root *Node, key int) *Node { var predecessor *Node current := root for current != nil { if key <= current.Val { current = current.Left } else { predecessor = current current = current.Right } } return predecessor }

💡 Hint

Look for missing closing braces or misplaced else statements.

Option A misses the closing brace for the if block before else, causing a syntax error.

🚀 Application

expert

Number of Nodes Visited to Find Inorder Predecessor

Given a balanced BST with 7 nodes (values 1 to 7), how many nodes will the inorderPredecessor function visit to find the predecessor of node with value 6?

DSA Go

func inorderPredecessor(root *Node, key int) *Node {
    var predecessor *Node
    current := root
    for current != nil {
        if key <= current.Val {
            current = current.Left
        } else {
            predecessor = current
            current = current.Right
        }
    }
    return predecessor
}

A 4

B 6

C 5

D 3

💡 Hint

Trace the path from root to the node and count nodes visited.

The function visits nodes 4, 3, and 5 in the path, updating predecessor accordingly. Total nodes visited are 4.