Binary tree vertical order traversal

Hash Table Tree Depth-First Search Breadth-First Search Sorting Binary Tree

57.8% acceptance

Mar 31, 2026

3467

354

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.

Solution

Rust

Time O(n log n)

Space O(n)

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;
use std::collections::{VecDeque, BTreeMap};
impl Solution {
  pub fn vertical_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    if root.is_none() { return vec![]; }
    let mut map: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    let mut queue = VecDeque::new();
    queue.push_back((root.unwrap(), 0i32));
    while let Some((node, col)) = queue.pop_front() {
      let n = node.borrow();
      map.entry(col).or_default().push(n.val);
      if let Some(ref left) = n.left {
        queue.push_back((left.clone(), col - 1));
      }
      if let Some(ref right) = n.right {
        queue.push_back((right.clone(), col + 1));
      }
    }
    map.into_values().collect()
  }
}