pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//! Level Order (BFS) Traversal for Binary Tree (Generic, Production-Grade)
//!
//! Returns the level order traversal (BFS) of a binary tree as a vector of vectors.
//!
//! # Type Parameters
//! * `T`: Node value type. Must implement `Clone`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::tree_algorithms::binary_tree_traversal::TreeNode;
//! use pofk_algorithm::tree_algorithms::level_order_traversal::*;
//! let root = Some(Box::new(TreeNode::new(1)));
//! let levels = level_order_traversal(&root);
//! ```
use crate::tree_algorithms::binary_tree_traversal::TreeNode;
use std::collections::VecDeque;

pub fn level_order_traversal<T: Clone>(root: &Option<Box<TreeNode<T>>>) -> Vec<Vec<T>> {
    let mut res = Vec::new();
    if root.is_none() { return res; }
    let mut queue = VecDeque::new();
    queue.push_back(root.as_ref());
    while !queue.is_empty() {
        let mut level = Vec::new();
        for _ in 0..queue.len() {
            if let Some(Some(node)) = queue.pop_front() {
                level.push(node.val.clone());
                if node.left.is_some() { queue.push_back(node.left.as_ref()); }
                if node.right.is_some() { queue.push_back(node.right.as_ref()); }
            }
        }
        if !level.is_empty() { res.push(level); }
    }
    res
}