Home / Data structures and Algorithms by Java Examples / Recursion / Tree Traversal without Recursion Using Stack Class in JAVA Example
Tree Traversal without Recursion Using Stack Class in JAVA Example
567 views.
TreeTraversalUsingStack.java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Staff is the class which has hierarchy structure of employee information.
 */

class Employee {
    public int id;
    public String name;
    
    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    public List<Employee> employees = new ArrayList<>();
}

class TreeTraversalUsingStack {
    /**
     * findEmployee is a method which is going to find employee within the hierarchy
     * using stack without recursion  
     *
     */
    static int findEmployee(Employee employee, int id) {
        Stack<Employee> stack = new Stack<>();
        stack.push(employee);
        
        while (stack.size() > 0) {
            Employee currentEmployee = stack.pop();
            
            System.out.println(id+">> checking with >>"+currentEmployee.id);
            if (currentEmployee.id == id) {
                return id;
            }
            
            for (Employee subEmployee : currentEmployee.employees) {
                stack.push(subEmployee);
            }
        }
        
        /**
         * not found anywhere
         */
        return 0;
        
    }
    public static void main(String[] args) {
        /*
         * Creating all three levels of employees.
         */
        Employee firstLevel = new Employee(1,"Sarathy");
        
        Employee secondLevel_1 = new Employee(2,"Laya");
        Employee secondLevel_2 = new Employee(3,"Vidhyaa");
        
        Employee thirdLevel_1 = new Employee(4, "Ram");
        Employee thirdLevel_2 = new Employee(5, "Raja");
        Employee thirdLevel_3 = new Employee(6, "Siva");
        Employee thirdLevel_4 = new Employee(7, "Kumar");
        
        /**
         * Linking third level employees to second level employees.
         */
        List<Employee> secondLevel_1_List = new ArrayList<>();
            secondLevel_1_List.add(thirdLevel_1);
            secondLevel_1_List.add(thirdLevel_2);
        secondLevel_1.employees = secondLevel_1_List;
            
        List<Employee> secondLevel_2_List = new ArrayList<>();
            secondLevel_2_List.add(thirdLevel_3);
            secondLevel_2_List.add(thirdLevel_4);
        secondLevel_2.employees = secondLevel_2_List;
        
        /**
         * Linking second level employees to first level employee.
         */
        List<Employee> firstLevel_List = new ArrayList<>();
            firstLevel_List.add(secondLevel_1);
            firstLevel_List.add(secondLevel_2);
        firstLevel.employees = firstLevel_List;
        
        
        /**
         * calling stack recursive iteration method to find employee id in the tree.
         */
        int foundId1 = findEmployee(firstLevel, 7);
        System.out.println(foundId1);
        
        int foundId2 = findEmployee(firstLevel, 4);
        System.out.println(foundId2);
    }
}
Output
7>> checking with >>1
7>> checking with >>3
7>> checking with >>7
7
4>> checking with >>1
4>> checking with >>3
4>> checking with >>7
4>> checking with >>6
4>> checking with >>2
4>> checking with >>5
4>> checking with >>4
4
Related Examples
   Simple Recursion Example in JAVA
   Print array using recursion JAVA Example
   Recursion on ArrayList Strings in JAVA Example
   Factorial Program using Recursion in JAVA Example
   Fibonacci Series using Recursion in JAVA Example
   Tree Traversal with Recursion in JAVA Example
   Tree Traversal without Recursion Using Stack Class in JAVA Example
   Is ArrayList Ordered using Recursion in JAVA Example
   Tower of Hanoi using Recursion in Java Example
Copyright © 2016 Learn by Examples, All rights reserved