Question 56 : How can you traverse binary tree?

 There are three ways to traverse a binary tree

• PreOrder

• InOrder

• PostOrder

PreOrder traversal:

In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.

Steps for PreOrder traversal are:

• Visit the node.
• Traverse the left subtree in PreOrder.
• Traverse the right subtree in PreOrder.

There can be two ways of implementing it.

• Recursive
• Iterative

Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be::

public void preorder(TreeNode root) {
    if(root !=  null) {
   //Visit the node by Printing the node data  
      System.out.printf("%d ",root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }

Iterative solution:
For recursion, we use the implicit stack. So here to convert the recursive solution to iterative, we will use the explicit stack.
Steps for iterative solution:

1. Create empty stack and pust root node to it.
2. Do the following when stack is not empty
   • Pop a node from stack and print it
   • Push right child of a popped node to stack
   • Push left child of a popped node to stack

We are pushing the right child first, so it will be processed after the left subtree as Stack is LIFO.:

public void preorderIter(TreeNode root) {
 
         if(root == null)
             return;
 
         Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(root);
 
         while(!stack.empty()){
 
             TreeNode n = stack.pop();
             System.out.printf("%d ",n.data);
 
             if(n.right != null){
                 stack.push(n.right);
             }
             if(n.left != null){
                 stack.push(n.left);
             }
 
         }
 
     }

Example:
Let's say your binary tree is

Let's create a java program for PreOrder traversal::

import java.util.Stack;
 
public class BinaryTreePreOrder {
 
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    // Recursive Solution
    public void preorder(TreeNode root) {
        if(root !=  null) {
            //Visit the node-Printing the node data  
            System.out.printf("%d ",root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }
 
    // Iterative solution
    public void preorderIter(TreeNode root) {
 
        if(root == null)
            return;
 
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
 
        while(!stack.empty()){
 
            TreeNode n = stack.pop();
            System.out.printf("%d ",n.data);
 
            if(n.right != null){
                stack.push(n.right);
            }
            if(n.left != null){
                stack.push(n.left);
            }
 
        }
 
    }
 
    public static void main(String[] args)
    {
        BinaryTreePreOrder bi=new BinaryTreePreOrder();
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Using Recursive solution:");
 
        bi.preorder(rootNode);
 
        System.out.println();
        System.out.println("-------------------------");
        System.out.println("Using Iterative solution:");
 
        bi.preorderIter(rootNode);
    }
 
    public static TreeNode createBinaryTree()
    {
 
        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
 
        rootNode.left=node20;
        rootNode.right=node60;
 
        node20.left=node10;
        node20.right=node30;
 
        node60.left=node50;
        node60.right=node70;
 
        return rootNode;
    }
}

Run the above program and you will get the following output::

Using Recursive solution:
40 20 10 30 60 50 70
————————-
Using Iterative solution:
40 20 10 30 60 50 70