Binary Tree PreOrder Traversal in Java

ghz 10months ago ⋅ 148 views

1. Introduction

Binary Tree PreOrder Traversal is a technique used to traverse all nodes of a binary tree in a specific order. In PreOrder Traversal, each node is visited before its children.

2. What is PreOrder Traversal?

PreOrder Traversal visits the nodes in the following order:

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

3. Process of PreOrder Traversal

The process of PreOrder Traversal can be described as follows:

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

4. Implementation

4.1 Recursive Solution

In the recursive approach, we can implement PreOrder 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 PreOrderTraversal {
    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("PreOrder Traversal:");
        preOrderTraversal(root);
    }

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

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

4.2 Iterative Solution

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

import java.util.*;

public class PreOrderTraversal {
    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("PreOrder Traversal:");
        preOrderTraversal(root);
    }

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

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

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");

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

5. Complete Java Program

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

6. Conclusion

PreOrder 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 PreOrder Traversal is essential for various tree-related algorithms and applications.

#algorithm