dsa/algorithms/tree_traversal.rs
1use std::collections::VecDeque;
2use crate::data_structures::tree::{BinaryTree};
3
4/// Performs a level-order traversal (breadth-first traversal) on a binary tree.
5///
6/// 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.
7///
8/// # Parameters
9/// - `tree`: An `Option<Box<BinaryTree<T>>>` representing the root of the binary tree.
10///
11/// # Returns
12/// A `Vec<T>` containing the values of the nodes in level-order.
13///
14/// # Time Complexity
15/// - `O(n)`, where n is the number of nodes in the tree.
16///
17/// # Space Complexity
18/// - `O(n)`, as the queue holds all the nodes at a given level.
19///
20/// # Examples
21/// ```
22/// use dsa::algorithms::tree_traversal::{level_order_traversal, pre_order_traversal};use dsa::data_structures::tree::{BinaryTree, TreeNode};
23///
24/// let left_left_tree = BinaryTree::new(TreeNode::new(4), None, None);
25/// let left_right_tree = BinaryTree::new(TreeNode::new(5), None, None);
26/// let right_left_tree = BinaryTree::new(TreeNode::new(6), None, None);
27/// let right_right_tree = BinaryTree::new(TreeNode::new(7), None, None);
28///
29/// let left_tree = BinaryTree::new(TreeNode::new(2), Some(Box::new(left_left_tree)), Some(Box::new(left_right_tree)));
30/// let right_tree = BinaryTree::new(TreeNode::new(3), Some(Box::new(right_left_tree)), Some(Box::new(right_right_tree)));
31///
32/// let tree = BinaryTree::new(TreeNode::new(1), Some(Box::new(left_tree)), Some(Box::new(right_tree)));
33/// let tree_ptr = Some(Box::new(tree));
34///
35/// let result = level_order_traversal(&tree_ptr);
36/// let expected: Vec<_> = vec![1, 2, 3, 4, 5, 6, 7].into_iter().collect();
37/// assert_eq!(result, expected);
38/// ```
39pub fn level_order_traversal<T: Clone>(tree: &Option<Box<BinaryTree<T>>>) -> Vec<T> {
40 let mut visited = Vec::new();
41 let mut queue = VecDeque::new();
42 if let Some(root) = tree {
43 queue.push_back(root);
44 while let Some(current) = queue.pop_front() {
45 visited.push(current.root.value.clone());
46 if let Some(left) = ¤t.left {
47 queue.push_back(left);
48 }
49 if let Some(right) = ¤t.right {
50 queue.push_back(right);
51 }
52 }
53 }
54 visited
55}
56
57/// Performs a pre-order traversal on a binary tree.
58///
59/// In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree.
60///
61/// # Parameters
62/// - `tree`: An `Option<Box<BinaryTree<T>>>` representing the root of the binary tree.
63///
64/// # Returns
65/// A `Vec<T>` containing the values of the nodes in pre-order.
66///
67/// # Time Complexity
68/// - `O(n)`, where n is the number of nodes in the tree.
69///
70/// # Space Complexity
71/// - `O(n)`, due to the recursion stack and storage of visited nodes.
72///
73/// # Examples
74/// ```
75/// use dsa::algorithms::tree_traversal::{in_order_traversal, pre_order_traversal};
76/// use dsa::data_structures::tree::{BinaryTree, TreeNode};
77///
78/// let left_left_tree = BinaryTree::new(TreeNode::new(4), None, None);
79/// let left_right_tree = BinaryTree::new(TreeNode::new(5), None, None);
80/// let right_left_tree = BinaryTree::new(TreeNode::new(6), None, None);
81/// let right_right_tree = BinaryTree::new(TreeNode::new(7), None, None);
82///
83/// let left_tree = BinaryTree::new(TreeNode::new(2), Some(Box::new(left_left_tree)), Some(Box::new(left_right_tree)));
84/// let right_tree = BinaryTree::new(TreeNode::new(3), Some(Box::new(right_left_tree)), Some(Box::new(right_right_tree)));
85///
86/// let tree = BinaryTree::new(TreeNode::new(1), Some(Box::new(left_tree)), Some(Box::new(right_tree)));
87/// let tree_ptr = Some(Box::new(tree));
88///
89/// let result = pre_order_traversal(&tree_ptr);
90///
91/// let expected: Vec<_> = vec![1, 2, 4, 5, 3, 6, 7].into_iter().collect();
92/// assert_eq!(result, expected);
93/// ```
94pub fn pre_order_traversal<T: Clone>(tree: &Option<Box<BinaryTree<T>>>) -> Vec<T> {
95 let mut visited: Vec<T> = Vec::new();
96 if let Some(boxed_tree) = tree {
97 let tree = &*boxed_tree;
98 visited.push(tree.root.value.clone());
99 visited.extend(pre_order_traversal(&tree.left));
100 visited.extend(pre_order_traversal(&tree.right));
101 }
102 visited
103}
104
105/// Performs an in-order traversal on a binary tree.
106///
107/// In in-order traversal, the left subtree is visited first, followed by the root node, and then the right subtree.
108///
109/// # Parameters
110/// - `tree`: An `Option<Box<BinaryTree<T>>>` representing the root of the binary tree.
111///
112/// # Returns
113/// A `Vec<T>` containing the values of the nodes in in-order.
114///
115/// # Time Complexity
116/// - `O(n)`, where n is the number of nodes in the tree.
117///
118/// # Space Complexity
119/// - `O(n)`, due to the recursion stack and storage of visited nodes.
120///
121/// # Examples
122/// ```
123/// use dsa::algorithms::tree_traversal::in_order_traversal;
124/// use dsa::data_structures::tree::{BinaryTree, TreeNode};
125///
126/// let left_left_tree = BinaryTree::new(TreeNode::new(4), None, None);
127/// let left_right_tree = BinaryTree::new(TreeNode::new(5), None, None);
128/// let right_left_tree = BinaryTree::new(TreeNode::new(6), None, None);
129/// let right_right_tree = BinaryTree::new(TreeNode::new(7), None, None);
130///
131/// let left_tree = BinaryTree::new(TreeNode::new(2), Some(Box::new(left_left_tree)), Some(Box::new(left_right_tree)));
132/// let right_tree = BinaryTree::new(TreeNode::new(3), Some(Box::new(right_left_tree)), Some(Box::new(right_right_tree)));
133///
134/// let tree = BinaryTree::new(TreeNode::new(1), Some(Box::new(left_tree)), Some(Box::new(right_tree)));
135/// let tree_ptr = Some(Box::new(tree));
136///
137/// let result = in_order_traversal(&tree_ptr);
138///
139/// let expected: Vec<_> = vec![4, 2, 5, 1, 6, 3, 7].into_iter().collect();
140/// assert_eq!(result, expected);
141pub fn in_order_traversal<T: Clone>(tree: &Option<Box<BinaryTree<T>>>) -> Vec<T> {
142 let mut visited: Vec<T> = Vec::new();
143 if let Some(boxed_tree) = tree {
144 let tree = &*boxed_tree;
145 visited.extend(in_order_traversal(&tree.left));
146 visited.push(tree.root.value.clone());
147 visited.extend(in_order_traversal(&tree.right));
148 }
149 visited
150}
151
152/// Performs an in-order traversal on a binary tree.
153///
154/// In in-order traversal, the left subtree is visited first, followed by the root node, and then the right subtree.
155///
156/// # Parameters
157/// - `tree`: An `Option<Box<BinaryTree<T>>>` representing the root of the binary tree.
158///
159/// # Returns
160/// A `Vec<T>` containing the values of the nodes in in-order.
161///
162/// # Time Complexity
163/// - `O(n)`, where n is the number of nodes in the tree.
164///
165/// # Space Complexity
166/// - `O(n)`, due to the recursion stack and storage of visited nodes.
167///
168/// # Examples
169/// ```
170/// use dsa::algorithms::tree_traversal::post_order_traversal;
171/// use dsa::data_structures::tree::{BinaryTree, TreeNode};
172///
173/// let left_left_tree = BinaryTree::new(TreeNode::new(4), None, None);
174/// let left_right_tree = BinaryTree::new(TreeNode::new(5), None, None);
175/// let right_left_tree = BinaryTree::new(TreeNode::new(6), None, None);
176/// let right_right_tree = BinaryTree::new(TreeNode::new(7), None, None);
177///
178/// let left_tree = BinaryTree::new(TreeNode::new(2), Some(Box::new(left_left_tree)), Some(Box::new(left_right_tree)));
179/// let right_tree = BinaryTree::new(TreeNode::new(3), Some(Box::new(right_left_tree)), Some(Box::new(right_right_tree)));
180///
181/// let tree = BinaryTree::new(TreeNode::new(1), Some(Box::new(left_tree)), Some(Box::new(right_tree)));
182/// let tree_ptr = Some(Box::new(tree));
183///
184/// let result = post_order_traversal(&tree_ptr);
185///
186/// let expected: Vec<_> = vec![4, 5, 2, 6, 7, 3, 1].into_iter().collect();
187/// assert_eq!(result, expected);
188/// ```
189pub fn post_order_traversal<T: Clone>(tree: &Option<Box<BinaryTree<T>>>) -> Vec<T> {
190 let mut visited: Vec<T> = Vec::new();
191 if let Some(boxed_tree) = tree {
192 let tree = &*boxed_tree;
193 visited.extend(post_order_traversal(&tree.left));
194 visited.extend(post_order_traversal(&tree.right));
195 visited.push(tree.root.value.clone());
196 }
197 visited
198}