In our previous post, we saw how to implement a binary search tree in Java and how to insert nodes in binary search tree.In this post, we will talk about the binary tree traversal. We will work on java code for traversing a binary tree in Java.
1. Binary Tree Traversal
Binary tree traversal differs from the linear data structure. In the linear data structure (e.g. Arrays, Linked list etc), we have only one logical way to traverse through them. We start from the beginning and move through each element. Binary tree is non-linear data structure, and it provides few different options for traversal. On a high level, we have the following 2 options for binary tree traversal in Java.
- Depth-First Traversal.
- Breadth First Search or Level Order Traversal
In this article we will focus on the binary tree traversal using depth first search.
2. Depth-First-Search
The depth-first search (DFS) is a tree traversal technique. In DFS, we go as deep as possible down to one path before we explore or visit the different node or the next sibling (It’s like a maze; you go to one end before exploring other side). Here is how the depth-first search will traverse the tree starting from root node.
If you look at the above picture, we are doing picking the one side of the tree and traversing it before going to the next side of the tree.There are few advantages of the depth-first search traversal.
- DFS on binary tree requires less memory than breadth-first search.
- It’s easy to implement (using recursion of loop).
There are three variations of the Depth-first traversal.
- In-order tree traversal.
- Preorder Tree traversal
- Postorder traversal
Let’s see how to implement these binary tree traversals in Java and what is the algorithm for these binary tree traversals.
2.1. Inorder Binary Tree Traversal
In the in-order binary tree traversal, we visit the left sub tree than current node and finally the right sub tree. Here is the high-level algorithm for BST in-order traversal.
1. Traverse the left sub-tree (keep visit the left sub tree until you reach leaf node).
2. Visit the current node.
3. Traverse the left sub-tree. (same as #1)
//pay attention to visit and traverseThe In order binary tree traversal will give the output in the ascending order. Therefore, we also call it in-order tree traversal.
This is how we can implement the in-order binary search tree traversal in Java.
public void inOrderTraversal() {
inOrderTraversal(root);
}
/*
Internal private method to do in order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path left-current-right
*/
private void inOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//Print the node
System.out.println(node.data);
//process the same step for the right node
inOrderTraversal(node.right);
}
}2.2. Preorder Binary Search Tree Traversal
The pre-order binary tree traversal involve visit the current node followed by left sub-tree and finally the right sub-tree. Here is a high-level algorithm for preorder BST traversal.
//Preorder BST tree traversal
1. Visit current node.
2. Traverse the left sub-tree.
3. Traverse right sub-tree.
//pay attention to visit and traverseHere are some well-known use cases where Preorder traversal is useful.
- Creating a copy of the tree.
- To get prefix expression of an expression tree.Read polish notation for more details.
Here is how we can implement the in-order binary tree traversal in Java.
public void preOrderTraversal() {
preOrderTraversal(root);
}
/*
Internal private method to do pre order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path current-left-right
*/
private void preOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//Print the node
System.out.println(node.data);
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//process the same step for the right node
inOrderTraversal(node.right);
}
}We are using recursion for these examples, you can also implement the same traversal using while loop.
2.3. Postorder Binary Tree Traversal
The post-order binary tree traversal, we traverse the left sub tree, the right sub-tree and finally visit the root node.Here is the algorithm for the post-order BST traversal.
//postorder algorithm.
1. Traverse the left sub tree.
2. Traverse the right sub tree.
3. Visit the nodein a post-order binary search tree traversal, the root is always the last node visited.
This is how we will implement the post-order traversal in binary tree in Java.
public void postOrderTraversal() {
postOrderTraversal(root);
}
/*
Internal private method to do post-order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path right-left-current
*/
private void postOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//process the same step for the right node
inOrderTraversal(node.right);
//Print the node
System.out.println(node.data);
}
}3. Binary Tree Traversal In Java
Here is the complete example for the binary search tree traversal (In order, Preorder and Postorder) in Java.
package com.javadevjournal.datastructure.tree.bst;
public class BinarySearchTree {
private Node root;
/**
* In order BST traversal allows to traverse tree in the sorted order.
* This traversal follow left->current-right pattern.
* <li>left sub-tree will be viisted first.</li>
* <li> Current node will be viisted after left traversal</li>
* <li>Right subtree will be visited in the end.</li>
*/
public void inOrderTraversal() {
inOrderTraversal(root);
}
public void postOrderTraversal() {
postOrderTraversal(root);
}
public void preOrderTraversal() {
preOrderTraversal(root);
}
/*
Internal private method to do in order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path left-current-right
*/
private void inOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//Print the node
System.out.println(node.data);
//process the same step for the right node
inOrderTraversal(node.right);
}
}
/*
Internal private method to do pre order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path current-left-right
*/
private void preOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//Print the node
System.out.println(node.data);
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//process the same step for the right node
inOrderTraversal(node.right);
}
}
/*
Internal private method to do post-order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path right-left-current
*/
private void postOrderTraversal(Node node) {
//We will continue until null or empty node is found
if (node != null) {
//visit the left subtree until the leaf node
inOrderTraversal(node.left);
//process the same step for the right node
inOrderTraversal(node.right);
//Print the node
System.out.println(node.data);
}
}
/**
* Internal node class representing the node of the BST. This contains the following information
* <li>data- actual data stored in the Tree</li>
* <li>left - Left child of the node</li>
* <li>right - right child of the node</li>
*/
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
//this just for reading.they will be null by default
this.left = null;
this.right = null;
}
}
}
// Main program to test it
package com.javadevjournal.datastructure.tree;
import com.javadevjournal.datastructure.tree.bst.BinarySearchTree;
public class BinarySearchTreeTest {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
/* We are building a BST as below
52
/ \
15 56
/ \ / \
9 16 54 61
/ \
3 10 */
bst.insert(52);
bst.insert(15);
bst.insert(56);
bst.insert(9);
bst.insert(16);
bst.insert(54);
bst.insert(3);
bst.insert(10);
bst.insert(61);
//inorder traversal
bst.inOrderTraversal(); //output [3,9,10,15,16,52,54,56,61]
//pre-order
bst.preOrderTraversal(); //output [52,15,9,3,10,16,56,54,61]
//post-order
bst.postOrderTraversal(); //output [3,10,9,16,15,54,61,56,52]
}
}Summary
In this article, we saw the binary tree traversal and how to implement the binary search tree traversal in Java. We covered the depth-first-search and how to perform in-order, preorder and post-order traversal. As always, the source code is available on GitHub.
typo in 2.2. Preorder BST TraversalSeems a copy paste error… its invoking the inorder function.