Classic 150 Interview Questions P230 Kth Smallest Element in a Binary Search Tree

---

Timeline

Timeline

2025-10-31

init

Inorder traversal

---

Problem:

P230 Kth in a Binary Search Tree K Smallest Element

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150

In-order traversal, return when reaching the kth element.

struct Solution;
// Definition for a binary tree node.
#[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
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    // Kth element in in-order traversal
    pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
        let mut stack = VecDeque::new();
        let mut p = root;
        let mut count = 0;
        let mut res = 0;

        while p.is_some() || !stack.is_empty(){
            if let Some(node) = p{
                stack.push_back(node.clone());
                p = node.borrow().left.clone();
            }else{
                count +=1;
                let curr = stack.pop_back().unwrap();
                if count == k{
                    res = curr.borrow().val;
                    break;
                }
                p = curr.borrow().right.clone();
            }
        }
        res
    }
}

fn main() {
    println!("Hello, world!");
}

leetcode hot 100 rewrite

#include <stack>
using std::stack;

class Solution {
    public:
        int kthSmallest(TreeNode *root, int k)
        {
                // 1 <= k <= n <= 10^4
                stack<TreeNode *> stk;

                TreeNode *p = root;
                int cnt = 0;

                while (p || !stk.empty()) {
                        if (p) {
                                stk.push(p);
                                p = p->left;
                        } else {
                                p = stk.top();
                                stk.pop();

                                cnt++;
                                if (cnt == k)
                                        break;

                                p = p->right;
                        }
                }

                return p->val;
        }
};