Tree Traversals: In-order, Pre-order, Post-order

Tree traversal is the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.) which have only one logical way to traverse them, trees can be traversed in different ways.

1. In-order Traversal

In an in-order traversal, we visit the left subtree, then the root, and finally the right subtree.

Algorithm:

  1. Recursively traverse the left subtree.
  2. Visit the root.
  3. Recursively traverse the right subtree.

Pseudocode:

inorder(node)
    if node is null, return
    inorder(node.left)
    visit(node)
    inorder(node.right)

Use Case:

In-order traversal is commonly used with Binary Search Trees (BST) as it visits nodes in ascending order.

2. Pre-order Traversal

In a pre-order traversal, we visit the root first, then the left subtree, and finally the right subtree.

Algorithm:

  1. Visit the root.
  2. Recursively traverse the left subtree.
  3. Recursively traverse the right subtree.

Pseudocode:

preorder(node)
    if node is null, return
    visit(node)
    preorder(node.left)
    preorder(node.right)

Use Case:

Pre-order traversal is used to create a copy of the tree or to get prefix expression on an expression tree.

3. Post-order Traversal

In a post-order traversal, we visit the left subtree, then the right subtree, and finally the root.

Algorithm:

  1. Recursively traverse the left subtree.
  2. Recursively traverse the right subtree.
  3. Visit the root.

Pseudocode:

postorder(node)
    if node is null, return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Use Case:

Post-order traversal is used when we want to delete the tree or to get the postfix expression of an expression tree.

Comparison and Time Complexity

Consider this binary tree:

    1
   / \
  2   3
 / \
4   5

Traversal results:

  • In-order: 4 2 5 1 3
  • Pre-order: 1 2 4 5 3
  • Post-order: 4 5 2 3 1

Time Complexity: All three traversals have a time complexity of O(n), where n is the number of nodes in the tree, as they visit each node exactly once.

Space Complexity: O(h) for the recursive call stack, where h is the height of the tree. In the worst case of a skewed tree, this could be O(n).

Note: These traversals can also be implemented iteratively using a stack, which can be beneficial in certain scenarios, especially when dealing with very deep trees where recursive approaches might lead to stack overflow.