Kth Smallest Element in BST in DSA Rust

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right. To find the kth smallest, we visit nodes in order from smallest to largest.

Analogy: Imagine a library where books are arranged from shortest to tallest on shelves. To find the kth shortest book, you walk along the shelves from left to right, counting books until you reach the kth one.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑ (root)

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find 3rd smallest element

Goal: Find the 3rd smallest value in the BST

Step 1: Start in-order traversal at root (5), go left to 3

2 -> 3 -> 4 -> 5 -> 7 -> 8
 ↑ at node 3

Why: Left subtree has smaller values, so we start there

Step 2: Go left from 3 to 2, visit 2 (1st smallest)

[2] -> 3 -> 4 -> 5 -> 7 -> 8

Why: 2 is the smallest node, count 1

Step 3: Back to 3, visit 3 (2nd smallest)

2 -> [3] -> 4 -> 5 -> 7 -> 8

Why: After left subtree, visit parent node

Step 4: Go right from 3 to 4, visit 4 (3rd smallest)

2 -> 3 -> [4] -> 5 -> 7 -> 8

Why: Next in order is right child, count 3rd smallest

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
3rd smallest element is 4

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    fn inorder(node: &Option<Rc<RefCell<TreeNode>>>, k: &mut i32, result: &mut Option<i32>) {
        if node.is_none() || result.is_some() {
            return; // stop if node is empty or result found
        }
        let n = node.as_ref().unwrap();
        inorder(&n.borrow().left, k, result); // traverse left subtree
        *k -= 1; // visit current node, decrease k
        if *k == 0 {
            *result = Some(n.borrow().val); // found kth smallest
            return;
        }
        inorder(&n.borrow().right, k, result); // traverse right subtree
    }

    let mut k_mut = k;
    let mut result = None;
    inorder(&root, &mut k_mut, &mut result);
    result.unwrap_or(-1) // return found value or -1 if not found
}

fn main() {
    // Build the BST
    let root = TreeNode::new(5);
    let node3 = TreeNode::new(3);
    let node7 = TreeNode::new(7);
    let node2 = TreeNode::new(2);
    let node4 = TreeNode::new(4);
    let node8 = TreeNode::new(8);

    root.borrow_mut().left = Some(node3.clone());
    root.borrow_mut().right = Some(node7.clone());
    node3.borrow_mut().left = Some(node2.clone());
    node3.borrow_mut().right = Some(node4.clone());
    node7.borrow_mut().right = Some(node8.clone());

    let k = 3;
    let kth_val = kth_smallest(Some(root), k);
    println!("{}th smallest element is {}", k, kth_val);
}

if node.is_none() || result.is_some() { return; }

stop traversal if node is empty or kth smallest found

inorder(&n.borrow().left, k, result);

traverse left subtree first to get smaller values

*k -= 1;

visit current node, decrease k count

if *k == 0 { *result = Some(n.borrow().val); return; }

if k reaches zero, record current node value as answer

inorder(&n.borrow().right, k, result);

traverse right subtree after visiting current node

Output

3th smallest element is 4

Complexity Analysis

Time: O(h + k) because we traverse down the tree height h and visit k nodes in order

Space: O(h) due to recursion stack for tree height h

vs Alternative: Compared to flattening the whole tree into a sorted list O(n), this approach stops early after k nodes, saving time

Edge Cases

Empty tree

Returns -1 as no kth smallest element exists

DSA Rust

if node.is_none() || result.is_some() { return; }

k larger than number of nodes

Returns -1 since kth element does not exist

DSA Rust

result.unwrap_or(-1)

k equals 1 (smallest element)

Returns the smallest node value correctly

DSA Rust

if *k == 0 { *result = Some(n.borrow().val); return; }

When to Use This Pattern

When asked for the kth smallest or largest element in a BST, use in-order traversal because it visits nodes in sorted order.

Common Mistakes

Mistake: Not stopping traversal after finding kth element, causing unnecessary work
Fix: Add a check to stop recursion once the kth element is found

Mistake: Using pre-order or post-order traversal which does not guarantee sorted order
Fix: Use in-order traversal to visit nodes in ascending order

Summary

Finds the kth smallest value in a binary search tree using in-order traversal.

Use when you need the kth smallest element without sorting all nodes explicitly.

The key insight is that in-order traversal visits nodes in ascending order, so counting nodes visited finds the kth smallest.

Practice

1. What does the Kth Smallest Element in BST problem ask you to find?

easy

A. The largest element in the BST

B. The element that is the Kth smallest when the BST elements are sorted

C. The root node of the BST

D. The height of the BST

Solution

1. Step 1: Understand BST property

   A Binary Search Tree (BST) stores elements so that left child nodes are smaller and right child nodes are larger.

2. Step 2: Define Kth smallest element

   The Kth smallest element is the element that appears in position K when all elements are sorted in ascending order.

3. Final Answer:

   The element that is the Kth smallest when the BST elements are sorted -> Option B

4. Quick Check:

   Kth smallest = Kth element in sorted order [OK]

Hint: Think sorted order of BST nodes in ascending order [OK]

Common Mistakes:

• Confusing Kth smallest with largest element
• Thinking root is always Kth smallest
• Mixing up height with element value

2. Which Rust code snippet correctly defines a BST node struct for the Kth smallest element problem?

easy

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

B. struct TreeNode { val: i32, left: TreeNode, right: TreeNode }

C. struct TreeNode { val: i32, left: &TreeNode, right: &TreeNode }

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

Solution

1. Step 1: Understand Rust ownership for trees

   Rust requires heap allocation for recursive types, so child nodes use Box wrapped in Option for nullable children.

2. Step 2: Check each struct definition

   Option is correct; direct TreeNode fields cause infinite size; references need lifetimes and are not owned.

3. Final Answer:

   struct TreeNode { val: i32, left: Option, right: Option } -> Option A

4. Quick Check:

   Use Option for child nodes [OK]

Hint: Use Option for recursive tree nodes in Rust [OK]

Common Mistakes:

• Using direct TreeNode fields causing infinite size error
• Using references without lifetimes
• Not wrapping children in Option for nullability

3. Given this Rust code snippet for inorder traversal to find the Kth smallest element, what will be printed?

fn inorder(root: &Option, k: &mut i32, result: &mut Option<i32>) {
    if let Some(node) = root {
        inorder(&node.left, k, result);
        *k -= 1;
        if *k == 0 {
            *result = Some(node.val);
            return;
        }
        inorder(&node.right, k, result);
    }
}

// BST: 3 <- 5 -> 7, k = 2
let root = Some(Box::new(TreeNode { val: 5, left: Some(Box::new(TreeNode { val: 3, left: None, right: None })), right: Some(Box::new(TreeNode { val: 7, left: None, right: None })) }));
let mut k = 2;
let mut result = None;
inorder(&root, &mut k, &mut result);
println!("{:?}", result);

medium

A. Some(5)

B. Some(3)

C. Some(7)

D. None

Solution

1. Step 1: Perform inorder traversal on BST

   Inorder visits nodes in ascending order: 3, 5, 7.

2. Step 2: Decrement k and check when k == 0

   Visit 3: k=2->1; Visit 5: k=1->0, result=5, stop traversal.

3. Final Answer:

   Some(5) -> Option A

4. Quick Check:

   2nd smallest in [3,5,7] is 5 [OK]

Hint: Inorder traversal gives sorted order; pick Kth visited node [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Not decrementing k correctly
• Not stopping traversal after finding Kth element

4. Identify the bug in this Rust function to find the Kth smallest element in a BST:

fn kth_smallest(root: &Option, k: &mut i32) -> Option<i32> {
    if let Some(node) = root {
        let left = kth_smallest(&node.left, k);
        *k -= 1;
        if *k == 0 {
            return Some(node.val);
        }
        let right = kth_smallest(&node.right, k);
        return right;
    }
    None
}

medium

A. The function does not handle the case when k is initially zero

B. The function does not decrement k before checking left subtree

C. The function does not return None when root is None

D. The function does not stop traversal after finding the Kth element

Solution

1. Step 1: Analyze traversal and return logic

   The function returns Some(value) when Kth element found, but recursive calls continue after that.

2. Step 2: Check if traversal stops after finding Kth element

   Because recursive calls continue, traversal does not stop immediately, causing unnecessary work or wrong results.

3. Final Answer:

   The function does not stop traversal after finding the Kth element -> Option D

4. Quick Check:

   Traversal must stop once Kth element found [OK]

Hint: Stop recursion immediately after finding Kth element [OK]

Common Mistakes:

• Not returning early after finding Kth element
• Incorrect k decrement order
• Ignoring None base case

5. You have a BST with nodes inserted in this order: 6, 2, 8, 0, 4, 7, 9, 3, 5. What is the 4th smallest element in this BST?

hard

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: List BST elements in sorted order

   Inorder traversal of BST gives sorted nodes: 0, 2, 3, 4, 5, 6, 7, 8, 9.

2. Step 2: Identify 4th smallest element

   The 4th element in this sorted list is 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Sorted nodes: 0,2,3,4,... 4th is 4 [OK]

Hint: Inorder traversal lists BST nodes sorted; pick Kth element [OK]

Common Mistakes:

• Counting nodes incorrectly
• Confusing insertion order with sorted order
• Off-by-one errors in K counting