Kth Smallest Element in BST in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function Call

What is the output of the following Rust function call to find the 3rd smallest element in the BST?

DSA Rust

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

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

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        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 i32) {
        if let Some(n) = node {
            inorder(&n.borrow().left, k, result);
            *k -= 1;
            if *k == 0 {
                *result = n.borrow().val;
                return;
            }
            inorder(&n.borrow().right, k, result);
        }
    }
    let mut k_mut = k;
    let mut result = -1;
    inorder(&root, &mut k_mut, &mut result);
    result
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(5)));
    root.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    root.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(6))));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(1))));

    println!("{}", kth_smallest(Some(root), 3));
}

A 3

B 2

C 4

D 5

💡 Hint

Remember that inorder traversal of BST gives sorted order.

The inorder traversal of the BST visits nodes in ascending order: 1, 2, 3, 4, 5, 6. The 3rd smallest element is 3.

🧠 Conceptual

intermediate

Understanding Inorder Traversal in BST

Why does inorder traversal help find the kth smallest element in a BST?

A Because inorder traversal visits nodes in ascending order of their values.

B Because inorder traversal visits nodes in descending order of their values.

C Because inorder traversal visits nodes randomly.

D Because inorder traversal visits only leaf nodes.

💡 Hint

Think about the BST property and how inorder traversal works.

Inorder traversal visits left subtree, then node, then right subtree, which for BST means visiting nodes in ascending order.

🔧 Debug

advanced

Identify the Error in Kth Smallest Implementation

What error will this Rust code produce when trying to find the kth smallest element?

DSA Rust

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

A The function will cause a compile-time error due to borrowing rules.

B The function will panic at runtime due to null pointer dereference.

C The function may not stop traversal after finding kth element, causing unnecessary work.

D The function returns incorrect kth smallest value always.

💡 Hint

Check if the recursion stops after finding the kth element.

The recursive calls continue even after kth element is found because return only exits current call, not all recursion.

❓ Predict Output

advanced

Output of Kth Smallest with k Larger Than Node Count

What is the output of the function call kth_smallest(root, 10) on the BST below? BST structure: 3 / \ 1 4 \ 2

DSA Rust

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

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

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        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 i32) {
        if let Some(n) = node {
            inorder(&n.borrow().left, k, result);
            *k -= 1;
            if *k == 0 {
                *result = n.borrow().val;
                return;
            }
            inorder(&n.borrow().right, k, result);
        }
    }
    let mut k_mut = k;
    let mut result = -1;
    inorder(&root, &mut k_mut, &mut result);
    result
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(3)));
    root.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    root.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(2))));

    println!("{}", kth_smallest(Some(root), 10));
}

A 10

B 4

C 2

D -1

💡 Hint

What happens if k is larger than the number of nodes?

The function initializes result to -1 and only updates it if kth element is found. Since k=10 is larger than node count=4, result remains -1.

🚀 Application

expert

Optimizing Kth Smallest Element Search in BST

Which data structure modification allows finding the kth smallest element in O(log n) time on average in a BST?

A Store all elements in a separate sorted array.

B Augment each node with the count of nodes in its left subtree.

C Use a stack to perform iterative inorder traversal every time.

D Convert BST to a linked list and traverse k nodes.

💡 Hint

Think about how to avoid full traversal each time.

By storing the size of left subtree at each node, we can decide whether to go left, right, or return current node in O(log n) time.

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