BST Inorder Successor in DSA Rust - Deep Dive

Overview - BST Inorder Successor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child's value is smaller while the right child's value is larger than the node's value. The inorder successor of a node in a BST is the node that comes immediately after it when the tree is traversed in order (left, root, right). Finding the inorder successor helps in many tasks like deleting nodes or navigating the tree in sorted order.

Why it matters

Without the concept of an inorder successor, it would be hard to move through a BST in sorted order efficiently. This would make operations like finding the next bigger number or deleting nodes more complex and slower. In real life, this means slower search and update operations in databases, file systems, or any software using BSTs for quick data access.

Where it fits

Before learning this, you should understand what a Binary Search Tree is and how inorder traversal works. After this, you can learn about deletion in BSTs, balanced BSTs like AVL or Red-Black trees, and other tree traversal techniques.

Mental Model

Core Idea

The inorder successor of a node in a BST is the next node visited after it in an inorder traversal, which is the smallest node larger than the given node.

Think of it like...

Imagine a line of people sorted by height. The inorder successor of a person is the very next taller person standing right after them in line.

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40
Successor of 15 is 20
Successor of 20 is 30

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a Binary Search Tree is and how its nodes are arranged.

A BST is a tree where each node has a value. For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps in searching efficiently. Example: - Root: 20 - Left child: 10 (less than 20) - Right child: 30 (greater than 20)

Result

You can quickly decide to go left or right when searching for a value.

Understanding the BST property is key to knowing why inorder traversal produces sorted order and how successors relate to node values.

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal visits nodes in sorted order in a BST.

Inorder traversal means: 1. Visit left subtree 2. Visit current node 3. Visit right subtree For the BST: 20 / \ 10 30 \ \ 15 40 The order visited is: 10 -> 15 -> 20 -> 30 -> 40

Result

The nodes are visited in ascending order of their values.

Knowing inorder traversal order helps you understand what 'next' means for a node in a BST.

3

Intermediate

Finding Successor When Right Child Exists

🤔Before reading on: If a node has a right child, do you think its successor is the right child itself or the smallest node in the right subtree? Commit to your answer.

Concept: If a node has a right child, its inorder successor is the smallest node in that right subtree.

For example, for node 20: - Right child is 30 - The smallest node in right subtree is 30 itself (since 30 has no left child) So successor of 20 is 30. If right child has left children, go left as far as possible to find the smallest node.

Result

You find the next bigger node by going right once, then all the way left.

Understanding this rule lets you quickly find successors without traversing the whole tree.

4

Intermediate

Finding Successor When No Right Child

🤔Before reading on: If a node has no right child, do you think its successor is in its left subtree or somewhere else? Commit to your answer.

Concept: If a node has no right child, its successor is one of its ancestors, specifically the lowest ancestor whose left child is also an ancestor of the node.

For example, for node 15: - No right child - Move up to parent 10 - 15 is right child of 10, so keep moving up - Next parent is 20 - 15 is in left subtree of 20 So successor of 15 is 20. This means moving up until you find a node that is left child of its parent.

Result

You find the successor by climbing up the tree until you find a node that is a left child of its parent.

Knowing this ancestor rule helps find successors without scanning the entire tree.

5

Intermediate

Implementing Successor Search in Code

Concept: Translate the rules into a step-by-step algorithm to find the inorder successor.

Algorithm: 1. If node has right child: - Go to right child - Then go left as far as possible - Return that node 2. Else: - Move up to parent until current node is left child of parent - Return that parent This requires nodes to have parent pointers or a way to track ancestors.

Result

You get a clear method to find the successor for any node in a BST.

Having a clear algorithm bridges theory and practice, enabling implementation in any language.

6

Advanced

Rust Code for BST Inorder Successor

🤔Before reading on: Do you think the Rust code should use recursion, iteration, or both to find the successor? Commit to your answer.

Concept: Implement the successor search efficiently in Rust using iteration and parent pointers.

```rust use std::rc::{Rc, Weak}; use std::cell::RefCell; #[derive(Debug)] struct Node { val: i32, left: Option>>, right: Option>>, parent: Option>>, } impl Node { fn inorder_successor(node: Rc>) -> Option>> { // If right child exists, go right then all left if let Some(right) = node.borrow().right.clone() { let mut current = right; while let Some(left) = current.borrow().left.clone() { current = left; } return Some(current); } // Else go up until node is left child let mut current = Rc::clone(&node); loop { let parent_weak = current.borrow().parent.clone(); if let Some(parent_weak) = parent_weak { if let Some(parent) = parent_weak.upgrade() { if let Some(ref left_rc) = parent.borrow().left { if Rc::ptr_eq(left_rc, ¤t) { return Some(parent); } } current = parent; } else { break; } } else { break; } } None } } ```

Result

The code returns the inorder successor node or None if no successor exists.

Implementing with Rust's ownership and borrowing rules deepens understanding of tree navigation and safe memory handling.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think the successor search always takes O(log n) time in a BST? Commit to your answer.

Concept: Explore edge cases like nodes without successors and analyze time complexity.

Edge cases: - The maximum node has no successor (returns None). - Nodes with no right child and no suitable ancestor. Performance: - In balanced BSTs, successor search is O(log n) because height is log n. - In skewed trees, worst case is O(n). Optimizations: - Using parent pointers avoids full tree traversal. - Without parent pointers, successor search requires root traversal.

Result

You understand when successor search is fast and when it can be slow.

Knowing performance and edge cases prepares you for real-world scenarios and helps choose the right data structure.

Under the Hood

The inorder successor search uses BST properties and tree structure. If a node has a right subtree, the successor is the leftmost node there because it is the smallest larger value. If no right subtree exists, the algorithm climbs up ancestors until it finds a node that is a left child of its parent, meaning the parent is the next larger node. This relies on parent pointers or a path from root to node.

Why designed this way?

This method leverages the BST's sorted property to avoid scanning the entire tree. Historically, parent pointers were added to nodes to enable upward traversal efficiently. Alternatives like full inorder traversal are slower. This design balances time and space, allowing quick successor queries without extra storage.

Node
 ├─ Left Subtree (smaller values)
 ├─ Right Subtree (larger values)
 └─ Parent

Successor search:
If Right Subtree:
  Go Right -> Go Left as far as possible
Else:
  Go Up until current node is Left child
  Return Parent

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder successor always the right child of the node? Commit to yes or no.

Common Belief: The inorder successor is always the right child of the node if it exists.

Reality: The inorder successor is the leftmost node in the right subtree, which may not be the immediate right child.

Why it matters: Assuming the successor is the right child can cause incorrect results when the right child has a left subtree.

Quick: If a node has no right child, is its successor always its parent? Commit to yes or no.

Common Belief: If a node has no right child, its successor is always its parent node.

Reality: The successor is the lowest ancestor for which the node is in the left subtree, which may be higher than the immediate parent or none if the node is the maximum.

Why it matters: Mistaking the parent as successor can lead to wrong answers or missing that no successor exists.

Quick: Does every node in a BST have an inorder successor? Commit to yes or no.

Common Belief: Every node in a BST has an inorder successor.

Reality: The maximum node in the BST has no inorder successor because no larger node exists.

Why it matters: Not handling this case can cause errors or null pointer exceptions in code.

Expert Zone

1

Parent pointers simplify successor search but increase memory usage and complexity in tree modifications.

2

In threaded binary trees, successor pointers are stored explicitly, making successor queries O(1).

3

In balanced BSTs, successor search is efficient, but in skewed trees, it can degrade to linear time.

When NOT to use

If the BST nodes do not have parent pointers and you cannot afford to store them, successor search requires starting from the root each time, which is less efficient. In such cases, consider using threaded binary trees or augmenting nodes with successor pointers. For very large datasets, balanced trees like AVL or Red-Black trees are preferred to keep operations fast.

Production Patterns

In databases and file systems, inorder successor logic is used to navigate sorted indexes efficiently. Parent pointers or threaded trees are common to speed up traversal. Successor search is also critical in implementing delete operations in BSTs, where the successor replaces the deleted node to maintain order.

Connections

Inorder Traversal

Builds-on

Understanding inorder traversal is essential because the successor is defined by the order nodes are visited in this traversal.

Balanced Binary Search Trees (AVL, Red-Black Trees)

Builds-on

Balanced BSTs maintain height to ensure successor search remains efficient, preventing worst-case linear time.

Linked List Next Pointer

Similar pattern

The inorder successor acts like a 'next' pointer in a linked list, connecting nodes in sorted order, which helps understand tree traversal as a linked sequence.

Common Pitfalls

#1 Assuming the inorder successor is always the right child.

Wrong approach:

if node.right.is_some() {
return node.right.clone();
}

Correct approach:

if let Some(mut right) = node.borrow().right.clone() {
while let Some(left) = right.borrow().left.clone() {
right = left;
}
return Some(right);
}

Root cause:

Misunderstanding that the successor is the smallest node in the right subtree, not necessarily the immediate right child.

#2 Returning parent as successor without checking if node is left child.

Wrong approach:

if node.right.is_none() {
return node.parent.clone();
}

Correct approach:

let mut current = node.clone();
loop {
let parent_weak = current.borrow().parent.clone();
if let Some(parent_weak) = parent_weak {
if let Some(parent) = parent_weak.upgrade() {
if let Some(ref left_rc) = parent.borrow().left {
if Rc::ptr_eq(left_rc, ¤t) {
return Some(parent);
}
}
current = parent;
} else {
break;
}
} else {
break;
}
}
return None;

Root cause:

Ignoring the rule that successor is the lowest ancestor where node is in left subtree.

#3 Not handling the case when node has no successor (maximum node).

Wrong approach:

fn inorder_successor(node: Rc>) -> Rc> {
// code that always returns a node
}

Correct approach:

fn inorder_successor(node: Rc>) -> Option>> {
// code that returns None if no successor
}

Root cause:

Assuming every node has a successor leads to runtime errors or invalid results.

Key Takeaways

The inorder successor of a BST node is the next node visited in inorder traversal, representing the smallest larger value.

If a node has a right child, the successor is the leftmost node in that right subtree; otherwise, it is found by moving up to the nearest ancestor where the node is in the left subtree.

Parent pointers or ancestor tracking are essential for efficient successor search without traversing from the root each time.

Edge cases like nodes without successors and skewed trees affect the correctness and performance of successor search.

Implementing successor search deepens understanding of BST structure, traversal, and real-world applications like database indexing and tree deletion.

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