Kth Smallest Element in BST in DSA Rust - Build from Scratch

Kth Smallest Element in BST

📖 Scenario: You are working with a binary search tree (BST) that stores numbers. You want to find the kth smallest number in this tree. This is useful when you want to quickly find a specific ranked value, like the 3rd smallest score in a game leaderboard.

🎯 Goal: Build a Rust program that creates a BST, sets a value k, and finds the kth smallest element in the BST using an in-order traversal.

📋 What You'll Learn

Create a BST with the exact nodes and structure given

Create a variable k with the exact value given

Implement an in-order traversal function to find the kth smallest element

Print the kth smallest element exactly as shown

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in ranking systems, like leaderboards, or when you want to find a specific percentile value in sorted data stored in a BST.

💼 Career

Understanding BST traversal and selection algorithms is important for software engineers working with databases, search engines, and any system that requires efficient data retrieval and ranking.

1

Create the BST nodes

Create a binary search tree with the following structure using Node structs and Option> for children. The root node should have value 5, with left child 3 and right child 7. The left child 3 has children 2 (left) and 4 (right). The right child 7 has children 6 (left) and 8 (right). Define the Node struct with value: i32, left: Option>, and right: Option>. Name the root variable root.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

// Create the BST root node here
// Your code here

Hint

Define the Node struct first. Then create the root variable with nested Some(Box::new(Node { ... })) for each child.

2

Set the value of k

Create a variable called k and set it to 3. This means we want to find the 3rd smallest element in the BST.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 4,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));

// Create variable k and set it to 3
// Your code here

Hint

Just add let k = 3; inside the main function after the BST creation.

3

Implement in-order traversal to find kth smallest

Write a function called kth_smallest that takes root: &Option> and k: usize and returns Option. Use in-order traversal (left, root, right) to visit nodes in ascending order. Use a mutable counter to track how many nodes have been visited. Return the value of the kth visited node. Call this function inside main with root and k.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn kth_smallest(root: &Option>, k: usize) -> Option {
    // Your code here
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 4,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));

    let k = 3;

    // Call kth_smallest here
    // Your code here
}

Hint

Use a helper function inorder inside kth_smallest to do the traversal. Keep track of how many nodes you visited with count. When count == k, save the node's value in result.

4

Print the kth smallest element

Print the kth smallest element found by kth_smallest. Use println!("{}", value) where value is the integer inside the Option. You can unwrap safely because k is valid.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn kth_smallest(root: &Option>, k: usize) -> Option {
    fn inorder(node: &Option>, k: usize, count: &mut usize, result: &mut Option) {
        if node.is_none() || result.is_some() {
            return;
        }
        let n = node.as_ref().unwrap();
        inorder(&n.left, k, count, result);
        *count += 1;
        if *count == k {
            *result = Some(n.value);
            return;
        }
        inorder(&n.right, k, count, result);
    }

    let mut count = 0;
    let mut result = None;
    inorder(root, k, &mut count, &mut result);
    result
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 4,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));

    let k = 3;

    let result = kth_smallest(&root, k);

    // Print the kth smallest element here
    // Your code here
}

Hint

Use println!("{}", result.unwrap()); to print the value inside the Option. We unwrap safely because k is valid.

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