Preorder Traversal in binary tree in java

What is Preorder Traversal ?

In preorder traversal , the root node is visited first, then the left subtree and finally the right subtree. Preorder traversal also used to get an prefix expression of an expression. In this article we will see how to perform preorder travesal using recursion in java.

Preorder Traversal in Binary Tree in Java

Preorder Traversal Example

Example for PreOrder Traversal in Binary Tree in Java

Steps to Find Preorder Traversal

    Here are some of the steps for tree traversal :
  • Step 1: First we will print the root element which is 10 in above example.
  • Step 2: Traverse the left subtree recursively. The only node on left subtree is 20 . So print it and move to the right subtree of root.
  • Step 3: 30 is the root of right sub-tree , therefore , print it and move to its left. 
  • Step 5: Print 40 which is the only element in left subtree and move to right of it’s parent.
  • Step 6: Print 50  which is the last element of the tree.
  • Step 7 : Therefore, the printing sequence will be 10,20,30,40,50.

Algorithm to find preorder traversal using recursion

   Algorithm  preorder(Tree):

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

CODE FOR PREORDER TRAVERSAL USING RECURSION

// Preorder Traversal in java 
/*Node class with left and right child and currend node and key value */
class Node
{
   Node left ,right;
   int value;
   Node(int value)
   {
       this.value=value;
       left=null;
       right=null;
   }
}
class Preorder
{
   Node root; //root of the binary tree
   Preorder()
   {
       root=null;
   }
   /*preorder traversal of binary tree */  
   public  void preorder(Node ptr)
   {
       if(ptr==null)
       return ;
       /*first print the value of node*/  
       System.out.print(ptr.value+" ");
       /*then traverse the left child */
       preorder(ptr.left);
       /*now traverse the right child*/
       preorder(ptr.right);
   }
   public static void main(String[] args)
   {
       Preorder t=new Preorder();
       t.root=new Node(10);
       t.root.left=new Node(20);
       t.root.right=new Node(30);
       t.root.right.left=new Node(40);
       t.root.right.right=new Node(50);
       t.preorder(t.root);
   }
}

Output:

10 20 30 40 50

TIME & SPACE Complexity for PreOrder Traversal of Binary Tree

Time Complexity

O(n)

Space Complexity

O(h)