Summary

Remember: pre_order_traversal visits nodes in root_left_right order. It is a depth_first_search method that starts at the tree's root and processes each node before its children. You can implement it with a recursive_implementation or a stack_based_implementation. Typical uses include prefix_notation, tree_copying, and tree_serialization. For a tree with n nodes, time_complexity is O(n); with height h, space_complexity is O(h). This order is also called nlr_order. Null or empty subtrees are skipped.