Implement Traverse a Binary tree in Preorder in Java Using Recursion

How to Implement traverse a Binary tree in Preorder in Java using Recursion

Table of Contents

Steps on Preorder Traversal Algorithm

visit the node
visit the left subtree
visit the right subtree

import java.util.Stack;
 
class Node
{
    int data;
    Node left, right;
 
    public Node(int key)
    {
        data = key;
        left = right = null;
    }
}
 
class Main
{
    
    public static void preorderIterative(Node root)
    {
        
        if (root == null) {
            return;
        }
    
        Stack<Node> stack = new Stack();
        stack.push(root);
    
        // loop till stack is empty
        while (!stack.empty())
        {
            // pop a node from the stack and print it
            Node curr = stack.pop();
    
            System.out.print(curr.data + " ");
    
           
            if (curr.right != null) {
                stack.push(curr.right);
            }
    
            
            if (curr.left != null) {
                stack.push(curr.left);
            }
    
            
            // is processed first (LIFO order)
        }
    }
 
    public static void main(String[] args)
    {
        
 
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
        root.right.left.left = new Node(7);
        root.right.left.right = new Node(8);
 
        preorderIterative(root);
    }
}

Output

                   1
                 /   \
                /     \
               2       3
              /      /   \
             /      /     \
            4      5       6
                  / \
                 /   \
                7     8

Leave a Comment

Your email address will not be published. Required fields are marked *