Tree Traversals - potatoscript/dsa GitHub Wiki

🧩 What is Tree Traversal?

Tree traversal is the process of visiting all the nodes in a tree, starting from the root node and following a particular order to visit all child nodes.

Why is Tree Traversal Important?

  • Searching: Traversals help us find elements in a tree structure.
  • Displaying: Traversals allow us to print or visualize tree structures in different ways.
  • Manipulation: We can modify or delete nodes in the tree using traversal.

🧩 Types of Tree Traversals

There are three main types of tree traversals:

  1. Pre-order Traversal: Visit the root node, then recursively visit the left subtree, and then the right subtree.
  2. In-order Traversal: Recursively visit the left subtree, then the root node, and finally the right subtree.
  3. Post-order Traversal: Recursively visit the left subtree, then the right subtree, and finally the root node.

Let's break them down with visual examples and step-by-step explanations.

🌳 1. Pre-order Traversal – Visit the Root First

In pre-order traversal, we follow this order:

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

Example: Pre-order Traversal of a Tree

Let’s consider the following binary tree:

         10
        /  \
       5    15
      / \     \
     2   7    20
  • Start at the root: 10 (visit it first).
  • Move to the left child: 5 (visit it).
  • Move to the left child of 5: 2 (visit it).
  • Now, go back to 5, then move to the right child of 5: 7 (visit it).
  • Now, go to the right child of 10: 15 (visit it).
  • Move to the right child of 15: 20 (visit it).

Pre-order Traversal: 10 β†’ 5 β†’ 2 β†’ 7 β†’ 15 β†’ 20

🌳 2. In-order Traversal – Visit Left, Then Root, Then Right

In in-order traversal, we follow this order:

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

Example: In-order Traversal of the Same Tree

         10
        /  \
       5    15
      / \     \
     2   7    20
  • Start at the root: 10.
  • Traverse the left subtree of 10, starting at 5:
    • Traverse left child of 5: 2 (visit it).
    • Visit 5.
    • Traverse right child of 5: 7 (visit it).
  • Visit 10.
  • Move to the right subtree of 10, starting at 15:
    • Visit 15.
    • Traverse the right child of 15: 20 (visit it).

In-order Traversal: 2 β†’ 5 β†’ 7 β†’ 10 β†’ 15 β†’ 20

🌳 3. Post-order Traversal – Visit Left, Then Right, Then Root

In post-order traversal, we follow this order:

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

Example: Post-order Traversal of the Same Tree

         10
        /  \
       5    15
      / \     \
     2   7    20
  • Start at the root: 10.
  • Traverse the left subtree of 10, starting at 5:
    • Traverse left child of 5: 2 (visit it).
    • Traverse right child of 5: 7 (visit it).
    • Visit 5.
  • Move to the right subtree of 10, starting at 15:
    • Traverse right child of 15: 20 (visit it).
    • Visit 15.
  • Finally, visit the root: 10.

Post-order Traversal: 2 β†’ 7 β†’ 5 β†’ 20 β†’ 15 β†’ 10

🧩 C# Code Examples for Tree Traversals

Let’s implement these tree traversal algorithms in C#!

πŸ“š Node Class (for Binary Tree)

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

πŸ“š Pre-order Traversal Method

public void PreOrderTraversal(TreeNode root)
{
    if (root == null)
        return;

    Console.Write(root.Value + " "); // Visit the root
    PreOrderTraversal(root.Left);    // Traverse left subtree
    PreOrderTraversal(root.Right);   // Traverse right subtree
}

πŸ“š In-order Traversal Method

public void InOrderTraversal(TreeNode root)
{
    if (root == null)
        return;

    InOrderTraversal(root.Left);     // Traverse left subtree
    Console.Write(root.Value + " "); // Visit the root
    InOrderTraversal(root.Right);    // Traverse right subtree
}

πŸ“š Post-order Traversal Method

public void PostOrderTraversal(TreeNode root)
{
    if (root == null)
        return;

    PostOrderTraversal(root.Left);   // Traverse left subtree
    PostOrderTraversal(root.Right);  // Traverse right subtree
    Console.Write(root.Value + " "); // Visit the root
}

🧩 Visualizing Tree Traversals

Now that we’ve explained and coded the three types of tree traversals, let’s visually represent how each one works.

  1. Pre-order Traversal (Root β†’ Left β†’ Right):
    Start at the root and move to the left child, then right child.
    ⬇️ Example: 10 β†’ 5 β†’ 2 β†’ 7 β†’ 15 β†’ 20

  2. In-order Traversal (Left β†’ Root β†’ Right):
    Traverse left first, then visit the root, then right.
    ⬇️ Example: 2 β†’ 5 β†’ 7 β†’ 10 β†’ 15 β†’ 20

  3. Post-order Traversal (Left β†’ Right β†’ Root):
    Traverse left, right, and then visit the root.
    ⬇️ Example: 2 β†’ 7 β†’ 5 β†’ 20 β†’ 15 β†’ 10

🧩 Time Complexity of Tree Traversals

The time complexity for all types of tree traversals (Pre-order, In-order, and Post-order) is:

  • O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once during traversal.

🧩 Applications of Tree Traversals

Tree traversals are crucial in many real-world applications. Here are some examples:

1. Expression Trees

In computer science, tree traversals are used to evaluate and process expression trees. For example, in the In-order Traversal, the result could be a mathematical expression in the proper order.

2. File Systems

File systems are often organized in tree-like structures, where directories are the parent nodes and files are the child nodes. Traversals allow you to list files and directories.

3. Binary Search Trees (BST)

Traversal is used to find the minimum or maximum value in a BST and to process data stored in an ordered way.