BST Inorder Successor in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor in a BST with right subtree

What is the output of the inorder successor function for node 15 in the given BST?

DSA Go

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

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    if p.Right != nil {
        curr := p.Right
        for curr.Left != nil {
            curr = curr.Left
        }
        return curr
    }
    var succ *TreeNode
    curr := root
    for curr != nil {
        if p.Val < curr.Val {
            succ = curr
            curr = curr.Left
        } else if p.Val > curr.Val {
            curr = curr.Right
        } else {
            break
        }
    }
    return succ
}

// BST structure:
//        20
//       /  \
//     10    30
//       \     \
//       15    40

// Call: inorderSuccessor(root, node with Val=15)

A Node with Val=20

B Node with Val=30

C Node with Val=40

D Node with Val=15

💡 Hint

Remember, if the node has a right child, the successor is the leftmost node in the right subtree.

Since node 15 has no right child, the successor is the lowest ancestor whose left child is also an ancestor of 15. That is node 20.

❓ Predict Output

intermediate

Inorder successor when node has no right subtree

What is the output of the inorder successor function for node 10 in the BST below?

DSA Go

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

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    var succ *TreeNode
    curr := root
    for curr != nil {
        if p.Val < curr.Val {
            succ = curr
            curr = curr.Left
        } else if p.Val > curr.Val {
            curr = curr.Right
        } else {
            break
        }
    }
    return succ
}

// BST structure:
//        20
//       /  \
//     10    30
//    /  
//   5

// Call: inorderSuccessor(root, node with Val=10)

A Node with Val=30

B Node with Val=5

C Node with Val=20

D Node with Val=10

💡 Hint

If the node has no right child, the successor is the lowest ancestor whose left child is also an ancestor of the node.

Node 10 has no right subtree, so the successor is the ancestor node 20 which is the next bigger value.

🔧 Debug

advanced

Identify the error in inorder successor code

What error will this code produce when finding the inorder successor of node 25 in the BST below?

DSA Go

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

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    if p.Right != nil {
        curr := p.Right
        for curr.Right != nil {
            curr = curr.Right
        }
        return curr
    }
    var succ *TreeNode
    curr := root
    for curr != nil {
        if p.Val < curr.Val {
            succ = curr
            curr = curr.Left
        } else if p.Val > curr.Val {
            curr = curr.Right
        } else {
            break
        }
    }
    return succ
}

// BST structure:
//        20
//       /  \
//     10    30
//           / \
//         25   40

// Call: inorderSuccessor(root, node with Val=25)

A Returns nil

B Returns node with Val=30

C Returns node with Val=25

D Returns node with Val=40

💡 Hint

Check the traversal inside the right subtree for the successor.

The code incorrectly traverses to the rightmost node in the right subtree instead of the leftmost. The successor of 25 is 30, and the code correctly returns it since 25 has no right subtree.

🧠 Conceptual

advanced

Inorder successor when node is the maximum element

What is the inorder successor of the maximum node in a BST?

A The minimum node in the BST

B The root node

C The parent of the maximum node

D Nil (no successor)

💡 Hint

Think about the inorder traversal order and what comes after the largest value.

The maximum node has no inorder successor because it is the last node in the inorder traversal.

🚀 Application

expert

Find inorder successor in BST without parent pointer

Given a BST and a node p without parent pointers, which approach correctly finds the inorder successor of p?

A Traverse from root, keep track of potential successor when moving left, return last recorded successor

B Traverse from p to root using parent pointers to find successor

C Return the right child of p if exists, else return p itself

D Traverse the entire tree inorder and return the node after p

💡 Hint

Without parent pointers, you must start from the root to find the successor.

Since p has no parent pointer, we start from root and move down. When moving left, we update successor. This finds the lowest ancestor whose left child is also ancestor of p.