Traversing of tree has different approach than that of linear data structures (Array, Linked List, Queues, Stacks, etc).

There are different ways to traversal a tree in DFS such as:

1. Preorder
2. Inorder
3. Postorder

Here in this article, we shall discuss steps and different approach of implementing Preorder tree traversal.

Steps for Preorder Tree Traversal are :

1) Visit the root.
2) Traverse the left subtree, i.e., call Preorder(left-subtree)
3) Traverse the right subtree, i.e., call Preorder(right-subtree)                                                 
Preorder Traversal of above tree is 10, 20, 40, 70, 50, 30, 60

Time Complexity: O(n)

There are two ways to implement Preorder Tree Traversal.

1) Recursive
2) Iterative

Recursive solution for Preorder Tree Traversal :

Recursive solution for Preorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is

1) Print root node
2) Traversal left node i.e preorder(root.left)
3) Traversal right node i.e preorder(root.right)

Code for recursive solution

package com.code2succeed.tree;

public class PreorderTraversal {

	public static class Node {
		private int data;
		private Node left;
		private Node right;
		
		public Node(int data) {
			this.data = data;
		}
	}
	
	public void preorder(Node root) {
		if(root != null) {
			//print root node
			System.out.print(root.data+" ");
			//Traversal left 
			preorder(root.left);
			//Traversal right
			preorder(root.right);
		}
	}
	
	public static void main(String[] args) {
		Node root = new Node(10);
		Node node20 = new Node(20);
		Node node30 = new Node(30);
		Node node40 = new Node(40);
		Node node50 = new Node(50);
		Node node60 = new Node(60);
		Node node70 = new Node(70);
		
		root.left = node20;
		root.right = node30;
		node20.left = node40;
		node20.right = node50;
		node40.left = node70; 
		node30.right = node60;
		
		PreorderTraversal pt = new PreorderTraversal();
		pt.preorder(root);
	}
}

Output

10 20 40 70 50 30 60

Iterative solution for Preorder Traversal

To implement iterative solution for preorder Traversal, we will be using Stack data structure.Algorithm for iterative solution is

1) Push the root to the stack
2) while stack is not empty do the following
   - pop the top node and print it.
   - push the right node of the popped node to the stack.
   - push the left node of the popped node to the stack.

Code for iterative solution

package com.code2succeed.tree;

import java.util.Stack;

public class PreorderTraversal {

	public static class Node {
		private int data;
		private Node left;
		private Node right;
		
		public Node(int data) {
			this.data = data;
		}
	}
	
	public void preorderIterative(Node root) {
		if(root == null) { return; }
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		
		while(!stack.isEmpty()) {
			Node top = stack.pop();
			System.out.print(top.data+" ");
			if(top.right != null) {
				stack.push(top.right);
			}
			if(top.left != null) {
				stack.push(top.left);
			}
		}
	}
	
	public static void main(String[] args) {
		Node root = new Node(10);
		Node node20 = new Node(20);
		Node node30 = new Node(30);
		Node node40 = new Node(40);
		Node node50 = new Node(50);
		Node node60 = new Node(60);
		Node node70 = new Node(70);
		
		root.left = node20;
		root.right = node30;
		node20.left = node40;
		node20.right = node50;
		node40.left = node70; 
		node30.right = node60;
		
		PreorderTraversal pt = new PreorderTraversal();
		pt.preorderIterative(root);
	}
}

Output

10 20 40 70 50 30 60

Download code for Preorder Tree Traversal

PreorderTraversal

Stay tuned for more updates and tutorials !!!