Function level_order_traversal

pub fn level_order_traversal<T: Clone>(
    tree: &Option<Box<BinaryTree<T>>>,
) -> Vec<T>

Performs a level-order traversal (breadth-first traversal) on a binary tree.

This traversal visits each level of the tree from top to bottom, left to right. It uses a queue to keep track of the nodes to visit.

Parameters

• tree: An Option<Box<BinaryTree<T>>> representing the root of the binary tree.

Returns

A Vec<T> containing the values of the nodes in level-order.

Time Complexity

• O(n), where n is the number of nodes in the tree.

Space Complexity

• O(n), as the queue holds all the nodes at a given level.

Examples

use dsa::algorithms::tree_traversal::{level_order_traversal, pre_order_traversal};use dsa::data_structures::tree::{BinaryTree, TreeNode};

let left_left_tree = BinaryTree::new(TreeNode::new(4), None, None);
let left_right_tree = BinaryTree::new(TreeNode::new(5), None, None);
let right_left_tree = BinaryTree::new(TreeNode::new(6), None, None);
let right_right_tree = BinaryTree::new(TreeNode::new(7), None, None);

let left_tree = BinaryTree::new(TreeNode::new(2), Some(Box::new(left_left_tree)), Some(Box::new(left_right_tree)));
let right_tree = BinaryTree::new(TreeNode::new(3), Some(Box::new(right_left_tree)), Some(Box::new(right_right_tree)));

let tree = BinaryTree::new(TreeNode::new(1), Some(Box::new(left_tree)), Some(Box::new(right_tree)));
let tree_ptr = Some(Box::new(tree));

let result = level_order_traversal(&tree_ptr);
let expected: Vec<_> = vec![1, 2, 3, 4, 5, 6, 7].into_iter().collect();
assert_eq!(result, expected);