Tree Traversals

Table of Contents 📚

• Introduction to Tree Traversals
• In-order Traversal
• Pre-order Traversal
• Post-order Traversal
• Example Illustration
• Java Implementation
• Time and Space Complexity
• Conclusion

Introduction to Tree Traversals

Traversal is a fundamental operation in which we visit all the nodes of a tree and perform some operation (such as a print operation) at each node. In this post, we’ll discuss three commonly used traversals for binary trees: in-order, pre-order, and post-order.

In-order Traversal

In in-order traversal, we traverse the left subtree first, then the root node, and finally the right subtree.

Pre-order Traversal

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

Post-order Traversal

In post-order traversal, we traverse the left subtree first, then the right subtree, and finally the root node.

Example Illustration

Here’s a simple binary tree with elements [1, 2, 3]. I’ll use this tree to illustrate how the traversals work:

      2
     / \
    1   3

In-order Traversal

Left -> Root -> Right
1, 2, 3

Pre-order Traversal

Root -> Left -> Right
2, 1, 3

Post-order Traversal

Left -> Right -> Root
1, 3, 2

Java Implementation 🛠️

Here’s a simple Java implementation for all three traversals:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class TreeTraversal {

    // In-order
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    // Pre-order
    public void preorder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    // Post-order
    public void postorder(TreeNode root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }
}

Time and Space Complexity 🛠️

• Time Complexity: O(n) for all traversals, as we visit each node once.
• Space Complexity: O(h), where h is the height of the tree. This space is required for the function call stack.

Conclusion 📝

Understanding these basic tree traversals can provide a strong foundation for solving more complex problems involving trees.

If you find this guide useful, please share with others, and spread the knowledge!