Inorder successor in bst

Tree Depth-First Search Binary Search Tree Binary Tree

51.2% acceptance

Mar 31, 2026

2649

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null. The successor of a node p is the node with the smallest key greater than p.val.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

// 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;
impl Solution {
  pub fn inorder_successor(root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    let p_val = p.as_ref().unwrap().borrow().val;
    let mut successor = None;
    let mut curr = root;
    while let Some(node) = curr {
      let val = node.borrow().val;
      if val > p_val {
        successor = Some(node.clone());
        curr = node.borrow().left.clone();
      } else {
        curr = node.borrow().right.clone();
      }
    }
    successor
  }
}