Find In Generic Tree

I/P:

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

100

O/P: true

1• First of all we check the data of the node at which we are standing. 

2• If the data matches the data of the node then we return true from here only. No further statement will run in such a case. 

3• A for loop is applied to access all the children of Node node one by one. 

4• Inside this for loop, we make a recursive call to each child until we find the data and store this result in variable fic (find in child). 

5• We check if this variable is true. It means that data was present in the child branch to which the last call was made. 

6• So we return true because there is no need to make further calls. As we have found the data. 

7• If fic were false then control comes out of the for loop and we return false.

package pep.Day29;

import java.io.*;
import java.util.*;

public class Find_In_GenericTrees {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static boolean find(Node node, int data) {
        if (node.data == data)
            return true;

        // faith: mere children yhe btae ki unme hai ya nhi
        for (Node child : node.children) {
            boolean bool = find(child, data);
            if (bool) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        int data = Integer.parseInt(br.readLine());

        Node root = construct(arr);
        boolean flag = find(root, data);
        System.out.println(flag);
        // display(root);
    }

}