Binary Tree Traversal Data Structure

In this tutorial we will learn how to Traverse a Binary Tree in different Traversal modes ways with some examples.

What is Binary Tree Traversal?

We get the values or elements of Binary Tree by Traversing it. Often we wish to process a binary tree “by visiting each of its nodes”.

Mode of Binary Tree Traversal

Basically there are four modes of Traversal, we will discuss each of them one by one with example. Mostly Recursion is used to Traverse the Tree. See the below examples:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Traversal

Traverse using the Recursion.

1. Preorder Traversal

We are traversing a Binary Tree, so first we need to create it. In the below examples we are creating Binary Tree first then traversing it using the different modes by Recursive function.

Explanation:
1. Traverse the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

Graph Representation

Answer: 1 2 4 5 3 6

Code Representation

``````
public class BinaryTreeBT {

static class Node {
int data;
Node left;
Node right;

Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

// creating binary tree
static class BinaryTree {
static int id = -1;

public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}

}

// preorder traversal
public static void preOrderTraversal(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}

public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);

preOrderTraversal(result);

}
}
``````

Answer: 1 2 4 5 3 6

2. Inorder Traversal

Explanation:
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

Graph Representation:

Answer: 4 2 5 1 3 6

Coding Representation

``````
public class BinaryTreeBT {

static class Node {
int data;
Node left;
Node right;

Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

// creating binary tree
static class BinaryTree {
static int id = -1;

public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}

}

// inorder traversal
public static void inorderTraversal(Node root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}

public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);

inorderTraversal(result);

}
}
``````

Answer: 4 2 5 1 3 6

3. Postorder Traversal

Explanation:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

By Graph

Answer: 4 5 2 6 3 1

Code

``````
public class BinaryTreeBT {

static class Node {
int data;
Node left;
Node right;

Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

// creating binary tree
static class BinaryTree {
static int id = -1;

public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}

}

// post order traversal
public static void postorder(Node root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}

public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);

postorder(result);

}
}
``````

Answer: 4 5 2 6 3 1

4. Level order Traversal Of Binary Tree

Explanation:
To print the Tree in level order using Recursive function to traverse all nodes of a level. Find height of tree and run depth first search and maintain current height, print nodes from every height root for 1 to height and match if current height is equal to height of the iteration, then print node’s data.

1
23
456

Code

``````
import javax.management.Query;
import java.util.*;;

public class BinaryTreeBT {

static class Node {
int data;
Node left;
Node right;

Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

// creating binary tree
static class BinaryTree {
static int id = -1;

public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}

}

// level traversal
public static void levelTraversal(Node root) {
if (root == null) {
return;
}

while (!q.isEmpty()) {
Node currNode = q.remove();
if (currNode == null) {
System.out.println();
if (q.isEmpty()) {
break;
} else {
}
} else {
System.out.print(currNode.data);
if (currNode.left != null) {
}
if (currNode.right != null) {
}
}
}

}

public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);

levelTraversal(result);

}
}
``````

1
23
456

Thank you for reaching out to this tutorial. You can comment in the comment section below for any doubt and query.