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.
Graphical
Answer:
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;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
q.add(null);
while (!q.isEmpty()) {
Node currNode = q.remove();
if (currNode == null) {
System.out.println();
if (q.isEmpty()) {
break;
} else {
q.add(null);
}
} else {
System.out.print(currNode.data);
if (currNode.left != null) {
q.add(currNode.left);
}
if (currNode.right != null) {
q.add(currNode.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);
levelTraversal(result);
}
}
Answer:
1
23
456
Thank you for reaching out to this tutorial. You can comment in the comment section below for any doubt and query.
Learn more about Tree Traversal.
