Tree Traversal

Tree traversal is the process of visiting all nodes in a tree data structure in a specific order. Traversal methods help in performing operations like printing, modifying, or evaluating nodes in various ways depending on the application’s requirements.

The three most common traversal methods for binary trees are: 1. In-Order Traversal 2. Pre-Order Traversal 3. Post-Order Traversal

Each traversal method has specific use cases and orders for visiting nodes, making them useful for different types of operations.

In-Order Traversal

In In-Order Traversal, nodes are visited in the following order:

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

Properties of In-Order Traversal:

• In-Order traversal of a Binary Search Tree (BST) results in nodes being visited in ascending order.
• It is commonly used to produce sorted outputs of tree data.

Recursive In-Order Traversal Code

class TreeNode:
    def __init__(self, value: int):
        self.value = value
        self.left = None
        self.right = None

def in_order_traversal(node: TreeNode) -> None:
    """
    Perform in-order traversal on the binary tree.
    - node: The current node in the tree
    """
    if node:
        in_order_traversal(node.left)
        print(node.value, end=" ")
        in_order_traversal(node.right)

# Example Usage
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
in_order_traversal(root)  # Output: 5 10 15

Pre-Order Traversal

In Pre-Order Traversal, nodes are visited in the following order: 1. Visit the root node. 2. Traverse the left subtree. 3. Traverse the right subtree.

Properties of Pre-Order Traversal:

• Pre-Order is used for copying a tree, as it processes the root before the subtrees.
• Commonly used to serialize a tree structure and to create a prefix expression in expression trees.

Recursive Pre-Order Traversal Code

def pre_order_traversal(node: TreeNode) -> None:
    """
    Perform pre-order traversal on the binary tree.
    - node: The current node in the tree
    """
    if node:
        print(node.value, end=" ")
        pre_order_traversal(node.left)
        pre_order_traversal(node.right)

# Example Usage
pre_order_traversal(root)  # Output: 10 5 15

Post-Order Traversal

In Post-Order Traversal, nodes are visited in the following order: 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit the root node.

Properties of Post-Order Traversal:

• Post-Order is useful when we need to delete or free nodes from a tree because it visits children before the root.
• It is also used to evaluate postfix expressions in expression trees.

Recursive Post-Order Traversal Code

def post_order_traversal(node: TreeNode) -> None:
    """
    Perform post-order traversal on the binary tree.
    - node: The current node in the tree
    """
    if node:
        post_order_traversal(node.left)
        post_order_traversal(node.right)
        print(node.value, end=" ")

# Example Usage
post_order_traversal(root)  # Output: 5 15 10

Traversal Examples on a Binary Tree

For a binary tree:

        10
       /  \
      5    15

In-Order Traversal: 5, 10, 15

Pre-Order Traversal: 10, 5, 15

Post-Order Traversal: 5, 15, 10