use std::collections::HashMap;
#[derive(Debug)]
struct TreeNode {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
impl TreeNode {
fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
fn insert(&mut self, val: i32) {
if val < self.val {
match self.left {
Some(ref mut left_node) => left_node.insert(val),
None => self.left = Some(Box::new(TreeNode::new(val))),
}
} else if val > self.val {
match self.right {
Some(ref mut right_node) => right_node.insert(val),
None => self.right = Some(Box::new(TreeNode::new(val))),
}
}
}
fn inorder(&self, vals: &mut Vec<i32>) {
if let Some(ref left_node) = self.left {
left_node.inorder(vals);
}
vals.push(self.val);
if let Some(ref right_node) = self.right {
right_node.inorder(vals);
}
}
fn find_next_higher(&self, val: i32) -> Option<i32> {
let mut successor = None;
let mut current = self;
loop {
if val < current.val {
successor = Some(current.val);
if let Some(ref left_node) = current.left {
current = left_node;
} else {
break;
}
} else {
if let Some(ref right_node) = current.right {
current = right_node;
} else {
break;
}
}
}
successor
}
}
fn main() {
// Insert values into BST
let mut root = TreeNode::new(4);
let values = [2, 6, 1, 3, 5, 7];
for &v in &values {
root.insert(v);
}
// Insert values into HashMap
let mut map = HashMap::new();
map.insert(4, "four");
map.insert(2, "two");
map.insert(6, "six");
map.insert(1, "one");
map.insert(3, "three");
map.insert(5, "five");
map.insert(7, "seven");
// Print BST inorder
let mut inorder_vals = Vec::new();
root.inorder(&mut inorder_vals);
let bst_str = inorder_vals.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(" -> ") + " -> null";
println!("BST inorder: {}", bst_str);
// Find next higher after 3 in BST
let next_higher = root.find_next_higher(3);
match next_higher {
Some(val) => println!("Next higher after 3 in BST: {}", val),
None => println!("No next higher found in BST"),
}
// HashMap lookup (no order)
println!("HashMap keys (unordered): {:?}", map.keys());
println!("Cannot find next higher directly in HashMap without scanning all keys.");
}
if val < self.val { ... } else if val > self.val { ... }
decide to insert left or right to keep BST sorted
fn inorder(&self, vals: &mut Vec<i32>) { ... }
collect BST values in sorted order
fn find_next_higher(&self, val: i32) -> Option<i32> { ... }
traverse BST to find smallest value greater than given val
for &v in &values { root.insert(v); }
build BST by inserting all values
store values in Hash Map without order
BST inorder: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Next higher after 3 in BST: 4
HashMap keys (unordered): {1, 2, 3, 4, 5, 6, 7}
Cannot find next higher directly in HashMap without scanning all keys.
