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.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest value larger than the given node

B. The node with the largest value smaller than the given node

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node that comes just before it in this ascending order, meaning it has the largest value smaller than the node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is largest smaller value in BST [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which of the following Go function signatures correctly represents a function to find the inorder predecessor in a BST node struct named Node?

easy

A. func inorderPredecessor(root *Node, key int) *Node

B. func inorderPredecessor(key int) Node

C. func inorderPredecessor(root Node, key int) Node

D. func inorderPredecessor(root *Node) int

Solution

1. Step 1: Analyze function parameters and return type

   The function needs the BST root pointer and the key to find predecessor for, and returns a pointer to the predecessor node.

2. Step 2: Match with options

   func inorderPredecessor(root *Node, key int) *Node matches this: it takes *Node root, int key, and returns *Node.

3. Final Answer:

   func inorderPredecessor(root *Node, key int) *Node -> Option A

4. Quick Check:

   Pointer root and key input, pointer node output [OK]

Hint: Use pointer receiver and return pointer for BST nodes [OK]

Common Mistakes:

• Passing root by value instead of pointer
• Returning node value instead of node pointer
• Missing key parameter to identify target node

3. Given the following BST and code snippet, what will be printed?

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

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

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

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

medium

A. No predecessor

B. 5

C. 15

D. 10

Solution

1. Step 1: Trace the inorderPredecessor function for key=15

   Start at root (20). Since 15 <= 20, move left to 10. Since 15 > 10, set predecessor=10, move right to 15. Since 15 <= 15, move left (nil). Loop ends.

2. Step 2: Return predecessor node value

   Predecessor is node with value 10, so print 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Largest smaller than 15 is 10 [OK]

Hint: Move left if key ≤ node, else update predecessor and move right [OK]

Common Mistakes:

• Returning the key itself as predecessor
• Confusing predecessor with successor
• Not updating predecessor correctly when moving right

4. The following Go function is intended to find the inorder predecessor of a node with value key in a BST. What is the bug?

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

medium

A. The function should return curr instead of predecessor

B. The predecessor variable should be reset inside the loop

C. The condition should be key <= curr.Val to handle equal keys correctly

D. The loop should use recursion instead of iteration

Solution

1. Step 1: Analyze the condition in the loop

   The current condition is key < curr.Val, which skips updating predecessor when key equals curr.Val.

2. Step 2: Correct the condition to include equality

   Changing to key <= curr.Val ensures that when key equals curr.Val, we move left without updating predecessor, which is correct for inorder predecessor logic.

3. Final Answer:

   The condition should be key <= curr.Val to handle equal keys correctly -> Option C

4. Quick Check:

   Use <= to handle equal keys properly [OK]

Hint: Use <= in condition to handle equal keys correctly [OK]

Common Mistakes:

• Using < instead of <= causes wrong predecessor for equal keys
• Resetting predecessor inside loop loses previous valid value
• Returning curr instead of predecessor returns wrong node

5. You have a BST where each node has a pointer to its parent. How would you find the inorder predecessor of a given node n efficiently without starting from the root? Choose the best approach.

hard

A. If n has a left child, find the rightmost node in its left subtree; else, move up using parent pointers until you find a node which is the right child of its parent

B. Always start from the root and do a full inorder traversal to find predecessor

C. If n has a right child, find the leftmost node in its right subtree; else, move up using parent pointers until you find a node which is the left child of its parent

D. Return the parent node directly as the predecessor

Solution

1. Step 1: Check if node has left subtree

   If n has a left child, the predecessor is the rightmost node in that left subtree.

2. Step 2: If no left child, move up using parent pointers

   Move up until you find a node that is the right child of its parent; that parent is the predecessor.

3. Final Answer:

   If n has left child, find rightmost in left subtree; else move up until node is right child -> Option A

4. Quick Check:

   Use left subtree or climb parents to find predecessor [OK]

Hint: Use left subtree or climb parents via right child link [OK]

Common Mistakes:

• Starting from root wastes time
• Confusing predecessor with successor logic
• Returning parent directly without checks