Function pre_order_traversal

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

Performs a pre-order traversal on a binary tree.

In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree.

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 pre-order.

Time Complexity

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

Space Complexity

• O(n), due to the recursion stack and storage of visited nodes.

Examples

use dsa::algorithms::tree_traversal::{in_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 = pre_order_traversal(&tree_ptr);

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