In this post we’ll see a Java program to do a Binary tree traversal using depth first search.
Binary tree traversal
For traversing a binary tree you can use one of the following-
- Breadth first search
- Depth first search
In the post Binary Tree Traversal Using Breadth First Search Java Program we have already seen Java implementation for binary tree traversal using breadth first search. Now we’ll see Java implementation for the binary tree traversal using depth first search.
Depth first search
Contrary to the breadth first search where nodes with in the same level are visited first in depth first search traversal is done by moving to next level of nodes. Control moves to the deepest node and then come back to the parent node when dead end is reached.
There are several orderings for depth first search of a binary tree- inorder, preorder and postorder which are easy to implement using recursion. Apart from that you can also write a depth first search program using a stack in non-recursive way. So, in this post we’ll see Recursive Java implementation of inorder, preorder and postorder traversal of binary tree as well as iterative (non-recursive) Java implementation.
Binary tree Inorder traversal Java program
Logic for Inorder traversal of binary search tree is as follows-
- Recursively traverse the left subtree.
- Visit the root node
- Recursively traverse the right subtree
Note that inorder traversal of the binary search tree visit the nodes in ascending order so inorder traversal is also used for tree sort.
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
Binary tree Preoder traversal Java program
Logic for preorder traversal of binary search tree is as follows-
- Visit the root node
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
Binary tree Postoder traversal Java program
Logic for postorder traversal of binary search tree is as follows-
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
- Visit the root node
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
Depth first search recursive Java program
Here is a complete Java program for traversing a binary tree using depth first search. In the program there are recursive methods for inorder traversal, preorder traversal and postorder traversal.
public class DFS {
// first node
private Node root;
DFS(){
root = null;
}
// Class representing tree nodes
static class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
public void displayData(){
System.out.print(value + " ");
}
}
public void insert(int i){
root = insert(root, i);
}
//Inserting node - recursive method
public Node insert(Node node, int value){
if(node == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < node.value){
node.left = insert(node.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > node.value){
node.right = insert(node.right, value);
}
return node;
}
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
public static void main(String[] args) {
DFS bst = new DFS();
bst.insert(50);
bst.insert(70);
bst.insert(30);
bst.insert(15);
bst.insert(35);
bst.insert(7);
bst.insert(22);
bst.insert(31);
bst.insert(62);
bst.insert(87);
System.out.println("Binary tree inorder traversal- ");
bst.inOrder(bst.root);
System.out.println("");
System.out.println("Binary tree postorder traversal- ");
bst.postOrder(bst.root);
System.out.println("");
System.out.println("Binary tree preorder traversal- ");
bst.preOrder(bst.root);
}
}
Output
Binary tree inorder traversal- 7 15 22 30 31 35 50 62 70 87 Binary tree postorder traversal- 7 22 15 31 35 30 62 87 70 50 Binary tree preorder traversal- 50 30 15 7 22 35 31 70 62 87
Depth first search Non-Recursive Java program
To write a Java program for depth first search of a binary tree using a non-recursive method a stack is used as stack is a Last In First Out (LIFO) data structure. Iterative Java implementation for inorder and preorder traversal is easy to understand.
Iterative Java implementation for post order traversal of binary tree is a bit complex, as you can see in recursive method the statement to display is after the recursive calls in post order traversal which makes iterative implementation a bit complex.
Here post order traversal iterative implementation is done using two stacks. In the first stack you add root, left, right and then add root first in the second stack and then the add order would be right and left in the second stack when popped from the first stack. Now popping from second stack would give you the post order of left, right, root.
Here is a complete Java program for traversing a binary tree using depth first search. In the program there are iterative methods for inorder traversal, preorder traversal and postorder traversal where stack is used as an auxiliary data structure.
public class DFS {
// first node
private Node root;
DFS(){
root = null;
}
// Class representing tree nodes
static class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
public void displayData(){
System.out.print(value + " ");
}
}
public void insert(int i){
root = insert(root, i);
}
//Inserting node - recursive method
public Node insert(Node node, int value){
if(node == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < node.value){
node.left = insert(node.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > node.value){
node.right = insert(node.right, value);
}
return node;
}
// For traversing in order
public void inOrder(){
if(root == null){
return;
}
Stack<Node> stack = new Stack<>();
Node current = root;
while(current != null || !stack.isEmpty()){
// traverse left subtree
while(current != null){
stack.push(current);
current = current.left;
}
current = stack.pop();
current.displayData();
current = current.right;
}
}
// Preorder traversal
public void preOrder(){
if(root == null){
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node node = stack.pop();
node.displayData();
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
// Postorder traversal
public void postOrder(){
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
// insert tree root into second stack so that it is last to be popped
Node node = s1.pop();
s2.push(node);
// now follow the post order of pushing the left and right child
if(node.left!=null){
s1.push(node.left);
}
if(node.right!=null){
s1.push(node.right);
}
}
while(!s2.isEmpty()){
s2.pop().displayData();
}
}
public static void main(String[] args) {
DFS bst = new DFS();
bst.insert(50);
bst.insert(70);
bst.insert(30);
bst.insert(15);
bst.insert(35);
bst.insert(7);
bst.insert(22);
bst.insert(31);
bst.insert(62);
bst.insert(87);
System.out.println("Binary tree inorder traversal- ");
bst.inOrder();
System.out.println("");
System.out.println("Binary tree postorder traversal- ");
bst.postOrder();
System.out.println("");
System.out.println("Binary tree preorder traversal- ");
bst.preOrder();
}
}
Output
Binary tree inorder traversal- 7 15 22 30 31 35 50 62 70 87 Binary tree postorder traversal- 7 22 15 31 35 30 62 87 70 50 Binary tree preorder traversal- 50 30 15 7 22 35 31 70 62 87
That's all for this topic Binary Tree Traversal Using Depth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment