Function post_order_traversal

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

Performs an in-order traversal on a binary tree.

In in-order traversal, the left subtree is visited first, followed by the root node, 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 in-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::post_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 = post_order_traversal(&tree_ptr);

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