How to do preorder traversal in Java

 We know that the trees are non linear data structure in which we organize our data in hierarchical form. Unlike array we can not traverse the binary tree using loops (for, while ). To do the traversal of the binary tree we need to use the recursion. We can traverse the tree in two ways.

1. Breadth First search

2. Depth first search

In case of breadth first search we traverse level wise first level 0 then level 1 and then 2 and it keep going.

While in case of depth first search we traverse by going depth wise. We can further divide this depth first search in three ways.

1. Inorder traversal

2. Preorder traversal

3. Postorder traversal

In this article we are going to see how can we implement the Preorder traversal in java.

Preorder Traversal : In this type of traversal first we access the root element then the left element then the right element. This is most used binary tree traversal.

Output : 1 2 4 3 5 6

Java Code :

class Node{

int data;

Node left;

Node right;

Node(int data){

this.data=data;

this.left=null;

this.right=null;

}

}

class HindiCodingCommunity{

public static void Preorder(Node root){

if(root!=null){

System.out.println(root.data+" ");

Preorder(root.left);

Preorder(root.right);

}

}

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);

Preorder(root);

}

}

Time Complexity : O(n)

Space Complexity : Theta(Height of Binary Tree)