BST Inorder Successor in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of node 15 in this BST

Given the BST below, what is the inorder successor of the node with value 15?

BST structure:

       20
      /  \
    10    30
      \     \
      15    40

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

// Function to find inorder successor of a given node value
fn inorder_successor(root: &Option<Box<TreeNode>>, p_val: i32) -> Option<i32> {
    let mut successor = None;
    let mut current = root.as_ref();
    while let Some(node) = current {
        if p_val < node.val {
            successor = Some(node.val);
            current = node.left.as_ref();
        } else {
            current = node.right.as_ref();
        }
    }
    successor
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 20,
        left: Some(Box::new(TreeNode {
            val: 10,
            left: None,
            right: Some(Box::new(TreeNode {
                val: 15,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(TreeNode {
            val: 30,
            left: None,
            right: Some(Box::new(TreeNode {
                val: 40,
                left: None,
                right: None,
            })),
        })),
    }));
    let result = inorder_successor(&root, 15);
    println!("{:?}", result);
}

A Some(30)

B None

C Some(15)

D Some(20)

💡 Hint

Inorder successor is the smallest node greater than the given node.

The inorder successor of 15 is 20 because 20 is the next larger node in the BST after 15.

❓ Predict Output

intermediate

Output of inorder successor for node 40 in BST

What is the output of the inorder_successor function when searching for the successor of node 40 in the BST below?

       25
      /  \
    15    50
   /  \     \
 10   22    70

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn inorder_successor(root: &Option<Box<TreeNode>>, p_val: i32) -> Option<i32> {
    let mut successor = None;
    let mut current = root.as_ref();
    while let Some(node) = current {
        if p_val < node.val {
            successor = Some(node.val);
            current = node.left.as_ref();
        } else {
            current = node.right.as_ref();
        }
    }
    successor
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 25,
        left: Some(Box::new(TreeNode {
            val: 15,
            left: Some(Box::new(TreeNode {
                val: 10,
                left: None,
                right: None,
            })),
            right: Some(Box::new(TreeNode {
                val: 22,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(TreeNode {
            val: 50,
            left: None,
            right: Some(Box::new(TreeNode {
                val: 70,
                left: None,
                right: None,
            })),
        })),
    }));
    let result = inorder_successor(&root, 40);
    println!("{:?}", result);
}

A Some(50)

B Some(70)

C None

D Some(25)

💡 Hint

Find the smallest node greater than 40.

40 is less than 50, so successor is updated to 50. The traversal moves left but no smaller successor found. So successor is 50.

🔧 Debug

advanced

Identify the error in this inorder successor function

What error will this Rust code produce when trying to find the inorder successor?

DSA Rust

fn inorder_successor(root: &Option<Box<TreeNode>>, p_val: i32) -> Option<i32> {
    let mut successor = None;
    let mut current = root.as_ref();
    while let Some(node) = current {
        if p_val > node.val {
            successor = Some(node.val);
            current = node.left.as_ref();
        } else {
            current = node.right.as_ref();
        }
    }
    successor
}

A Returns None always

B Causes infinite loop

C Returns wrong successor value

D Compilation error due to borrow checker

💡 Hint

Check the comparison direction and subtree traversal.

The condition is reversed. It updates successor when p_val > node.val and moves left, which is incorrect logic for inorder successor.

🧠 Conceptual

advanced

Inorder successor when node has right subtree

In a BST, if a node has a right child, what is the inorder successor of that node?

A The rightmost node in the left subtree

B The leftmost node in the right subtree

C The parent node

D The right child itself

💡 Hint

Think about inorder traversal order.

The inorder successor of a node with a right subtree is the smallest node in that right subtree, which is the leftmost node there.

🚀 Application

expert

Find inorder successor in BST without parent pointers

Given a BST and a target node value, how can you find the inorder successor without using parent pointers?

Choose the correct approach.

A All of the above combined

B Traverse from target node to right child and then leftmost node

C Traverse from root, keep track of potential successor when moving left

D Use a stack to do inorder traversal until target is found, then next node is successor

💡 Hint

Think about how inorder successor is found in different cases.

Finding inorder successor without parent pointers requires combining approaches: if right subtree exists, go there and find leftmost node; else traverse from root keeping track of successor; or do inorder traversal with stack.

Practice

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

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which means the smallest node with a key greater than the current node.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = next bigger node [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Ignoring BST property in definition

2. Which Rust function signature correctly represents a method to find the inorder successor of a BST node?

easy

A. fn inorder_successor(root: &Option, p: &TreeNode) -> Option<&TreeNode>

B. fn inorder_successor(root: TreeNode, p: TreeNode) -> TreeNode

C. fn inorder_successor(root: &mut TreeNode, p: &mut TreeNode) -> TreeNode

D. fn inorder_successor(root: Option<TreeNode>, p: Option<TreeNode>) -> Option<TreeNode>

Solution

1. Step 1: Understand Rust ownership and references

   BST nodes are usually wrapped in Option to allow null and heap allocation. Passing references avoids ownership transfer.

2. Step 2: Analyze function signature correctness

   Option<&TreeNode> as return type allows returning a reference to a node or None. Input parameters as references to avoid moving ownership.

3. Final Answer:

   fn inorder_successor(root: &Option, p: &TreeNode) -> Option<&TreeNode> -> Option A

4. Quick Check:

   Use references and Option for safe BST traversal [OK]

Hint: Use references and Option types for BST nodes in Rust [OK]

Common Mistakes:

• Passing nodes by value causing ownership errors
• Returning owned nodes instead of references
• Using mutable references unnecessarily

3. Given the following Rust code snippet for finding the inorder successor, what will be printed?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn inorder_successor(root: &Option, p_val: i32) -> Option<i32> {
    let mut successor = None;
    let mut current = root;
    while let Some(node) = current {
        if p_val < node.val {
            successor = Some(node.val);
            current = &node.left;
        } else {
            current = &node.right;
        }
    }
    successor
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 20,
        left: Some(Box::new(TreeNode {
            val: 10,
            left: None,
            right: Some(Box::new(TreeNode {
                val: 15,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(TreeNode {
            val: 30,
            left: None,
            right: None,
        })),
    }));
    let result = inorder_successor(&root, 15);
    println!("{:?}", result);
}

medium

A. None

B. Some(20)

C. Some(15)

D. Some(30)

Solution

1. Step 1: Trace the search for successor of node with value 15

   Start at root (20). Since 15 < 20, successor = 20, move left to node 10. 15 > 10, move right to node 15.

2. Step 2: Continue traversal and finalize successor

   At node 15, 15 == 15, move right which is None. Loop ends. Last successor recorded is 20.

3. Final Answer:

   Some(20) -> Option B

4. Quick Check:

   Next bigger than 15 is 20 [OK]

Hint: Successor is smallest bigger node found going left [OK]

Common Mistakes:

• Returning the node itself as successor
• Confusing left and right subtree traversal
• Not updating successor when moving left

4. The following Rust function aims to find the inorder successor of a node in a BST but has a bug. What is the bug?

fn inorder_successor(root: &Option, p_val: i32) -> Option<i32> {
    let mut successor = None;
    let mut current = root;
    while let Some(node) = current {
        if p_val <= node.val {
            successor = Some(node.val);
            current = &node.left;
        } else {
            current = &node.right;
        }
    }
    successor
}

medium

A. Not handling None case for root

B. Function returns value instead of reference

C. Successor should be updated only when p_val > node.val

D. Using <= instead of < causes incorrect successor when p_val equals node.val

Solution

1. Step 1: Analyze condition p_val <= node.val

   Using <= means successor updates even when p_val equals node.val, which incorrectly sets successor to the node itself.

2. Step 2: Correct condition for successor update

   Successor should update only when p_val < node.val to find the next bigger node, not the node itself.

3. Final Answer:

   Using <= instead of < causes incorrect successor when p_val equals node.val -> Option D

4. Quick Check:

   Use < for successor update, not <= [OK]

Hint: Use strict less than (<) to avoid self as successor [OK]

Common Mistakes:

• Confusing < and <= in comparisons
• Ignoring edge case when p_val equals node.val
• Not testing with equal values

5. You have a BST where each node has a parent pointer in addition to left and right children. How can you find the inorder successor of a given node p efficiently using this extra pointer?

hard

A. Successor is always the right child of p

B. Always go to the root and perform inorder traversal to find successor

C. If p has right child, successor is leftmost node in right subtree; else go up using parent until node is left child

D. Use a stack to store nodes and pop until successor is found

Solution

1. Step 1: Check if node has right subtree

   If p has a right child, the successor is the leftmost node in that right subtree.

2. Step 2: If no right child, use parent pointer

   Move up the tree using parent pointers until you find a node which is the left child of its parent; that parent is the successor.

3. Final Answer:

   If p has right child, successor is leftmost node in right subtree; else go up using parent until node is left child -> Option C

4. Quick Check:

   Use right subtree or climb parents to find successor [OK]

Hint: Use parent pointer to climb up when no right child [OK]

Common Mistakes:

• Ignoring parent pointer advantage
• Assuming successor is always right child
• Performing full traversal unnecessarily