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

Steps on Preorder traversal algorithm

• visit the node
• visit the left subtree
• visit the right subtree

``````import java.util.Stack;

// Data structure to store a binary tree node
class Node
{
int data;
Node left, right;

// Function to create a new binary tree node having a given key
public Node(int key)
{
data = key;
left = right = null;
}
}

class Main
{
// Iterative function to perform preorder traversal on the tree
public static void preorderIterative(Node root)
{
// return if the tree is empty
if (root == null) {
return;
}

// create an empty stack and push the root node
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 + " ");

// push the right child of the popped node into the stack
if (curr.right != null) {
stack.push(curr.right);
}

// push the left child of the popped node into the stack
if (curr.left != null) {
stack.push(curr.left);
}

// the right child must be pushed first so that the left child
// 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
``````