Binary Tree PostOrder Traversal in Java

ghz 10months ago ⋅ 178 views

1. Introduction

Binary Tree PostOrder Traversal is a technique used to traverse all nodes of a binary tree in a specific order. In PostOrder Traversal, each node's children are visited before the node itself.

2. What is PostOrder Traversal?

PostOrder Traversal visits the left subtree, then the right subtree, and finally the root node. It starts from the leftmost leaf node, traverses all nodes in the left subtree, then traverses all nodes in the right subtree, and finally visits the root node.

3. Process of PostOrder Traversal

The process of PostOrder Traversal can be described as follows:

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

4. Implementation

4.1 Recursive Solution

In the recursive approach, we can implement PostOrder Traversal using a recursive function. Here's the code:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class PostOrderTraversal {
    public static void main(String[] args) {
        // Example binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("PostOrder Traversal:");
        postOrderTraversal(root);
    }

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

        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

4.2 Iterative Solution

In the iterative approach, we can implement PostOrder Traversal using a stack. Here's the code:

import java.util.*;

public class PostOrderTraversal {
    public static void main(String[] args) {
        // Example binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("PostOrder Traversal:");
        postOrderTraversal(root);
    }

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

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        Stack<TreeNode> result = new Stack<>();

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            result.push(curr);

            if (curr.left != null) stack.push(curr.left);
            if (curr.right != null) stack.push(curr.right);
        }

        while (!result.isEmpty()) {
            System.out.print(result.pop().val + " ");
        }
    }
}

5. Complete Java Program

The complete Java program demonstrating both recursive and iterative solutions for PostOrder Traversal is provided above.

6. Conclusion

PostOrder Traversal is a fundamental traversal technique used to visit all nodes of a binary tree in a specific order. It can be implemented using both recursive and iterative approaches. Understanding PostOrder Traversal is essential for various tree-related algorithms and applications.

#algorithm