Thursday, March 21, 2019

Binary Tree Traversal Using Depth First Search Java Program

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-

  1. Breadth first search
  2. 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

  1. Java Program to Delete a Node From Binary Search Tree (BST)
  2. Deque Implementation in Java Using Doubly Linked List
  3. Heap Sort Program in Java
  4. Find Largest and Second Largest Number in Given Array - Java Program
  5. How to Run a Shell Script From Java Program

You may also like-

  1. Difference Between Two Dates in Java
  2. Converting String to float - Java Program
  3. How to Read File From The Last Line in Java
  4. Converting float to int in Java
  5. Adding Tomcat Server to Eclipse
  6. Invoke Method at Runtime Using Java Reflection API
  7. Try-With-Resources in Java With Examples
  8. Spring MessageSource Internationalization (i18n) Support