Java Program for Tree Traversals

This Java program implements in-order, pre-order, and post-order traversals of a binary tree. Each type of traversal is used to visit all the nodes in a specific order, crucial for various applications such as expression tree evaluations and syntax tree processing in compilers.

Binary Tree Class

The BinaryTree class defines the structure of a binary tree node and includes methods for each traversal technique.

public class BinaryTree {
    static class Node {
        int value;
        Node left, right;

        public Node(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }

    Node root;

    public BinaryTree() {
        root = null;
    }

    // Method for In-Order Traversal
    public void inOrder(Node node) {
        if (node == null)
            return;
        
        inOrder(node.left); // Traverse left subtree
        System.out.print(node.value + " "); // Visit node
        inOrder(node.right); // Traverse right subtree
    }

    // Method for Pre-Order Traversal
    public void preOrder(Node node) {
        if (node == null)
            return;

        System.out.print(node.value + " "); // Visit node
        preOrder(node.left); // Traverse left subtree
        preOrder(node.right); // Traverse right subtree
    }

    // Method for Post-Order Traversal
    public void postOrder(Node node) {
        if (node == null)
            return;

        postOrder(node.left); // Traverse left subtree
        postOrder(node.right); // Traverse right subtree
        System.out.print(node.value + " "); // Visit node
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("In-order traversal:");
        tree.inOrder(tree.root);
        
        System.out.println("\nPre-order traversal:");
        tree.preOrder(tree.root);

        System.out.println("\nPost-order traversal:");
        tree.postOrder(tree.root);
    }
}

Explanation of the Traversal Methods

• In-order traversal visits the nodes in a left-root-right sequence which is useful for binary search trees where such a traversal outputs the values in a sorted order.
• Pre-order traversal visits the root node first followed by left and right subtrees. It’s used to create a copy of the tree or to serialize the tree structure.
• Post-order traversal visits the root node last, after its subtrees. This order is useful for deleting or freeing spaces because it ensures that children nodes are processed before their respective parent nodes.

Conclusion

The above Java program effectively demonstrates how to implement and utilize different tree traversal techniques, each serving unique purposes in various applications of computer science.