import java.util.ArrayList;
import java.util.List;

/**
 * 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<>();
}

public class TreeTraversalUsingRecursion {
    /**
     * findEmployee with recursion   
     *
     */
    static int findEmployee(Employee employee, int id) {
        /* Base Case */
        System.out.println(id+">>Testing with>>"+employee.id);
        if (id == employee.id) {
            System.out.println("Found returning: "+id);
            return id;
        }
        
        /* Recursion Case */
        for (Employee subEmployee : employee.employees) {
            int result = findEmployee(subEmployee, id);
            
            if (result != 0) {
                /* id is found */
                System.out.println("Found in return call: "+result);
                return result;
            }
        }
        
        /* Not found at any place */
        System.out.println("Not found in any place....");
        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);
    }
}