Find and Node to root path In Binary Tree

I/P:

19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n 30

O/P:

true [30, 37, 25, 50]

package pep.Day32;

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

public class Find_And_Node_to_rootpath_In_BinaryTree {
    public static class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public static class Pair {
        Node node;
        int state;

        Pair(Node node, int state) {
            this.node = node;
            this.state = state;
        }
    }

    public static Node construct(Integer[] arr) {
        Node root = new Node(arr[0], null, null);
        Pair rtp = new Pair(root, 1);

        Stack<Pair> st = new Stack<>();
        st.push(rtp);

        int idx = 0;
        while (st.size() > 0) {
            Pair top = st.peek();
            if (top.state == 1) {
                idx++;
                if (arr[idx] != null) {
                    top.node.left = new Node(arr[idx], null, null);
                    Pair lp = new Pair(top.node.left, 1);
                    st.push(lp);
                } else {
                    top.node.left = null;
                }

                top.state++;
            } else if (top.state == 2) {
                idx++;
                if (arr[idx] != null) {
                    top.node.right = new Node(arr[idx], null, null);
                    Pair rp = new Pair(top.node.right, 1);
                    st.push(rp);
                } else {
                    top.node.right = null;
                }

                top.state++;
            } else {
                st.pop();
            }
        }

        return root;
    }

    public static void display(Node node) {
        if (node == null) {
            return;
        }

        String str = "";
        str += node.left == null ? "." : node.left.data + "";
        str += " <- " + node.data + " -> ";
        str += node.right == null ? "." : node.right.data + "";
        System.out.println(str);

        display(node.left);
        display(node.right);
    }

    public static boolean find(Node node, int data) {
        // write your code here
        if (node == null) {
            return false;
        }

        return node.data == data ?
                true :
                find(node.left, data) || find(node.right, data);
    }

    public static ArrayList<Integer> nodeToRootPath(Node node, int data) {
        // we will check we got the data or not, and add into array list
        if (node == null || node.data == data) {
            ArrayList<Integer> base = new ArrayList<Integer>();
            if (node != null) {
                base.add(data);
            }
            return base;
        }

        // I've reached here, means data not found in node,
        // hence, now goto left, if data found add parent to array list
        ArrayList<Integer> left = nodeToRootPath(node.left, data);
        if (!left.isEmpty()) {
            left.add(node.data);
            return left;
        }

        ArrayList<Integer> right = nodeToRootPath(node.right, data);
        if (!right.isEmpty()) {
            right.add(node.data);
            return right;
        }
        
        // yha tak mujhe data nhi mila, return empty array list
        return new ArrayList<Integer>();
    }

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

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

        Node root = construct(arr);
        boolean found = find(root, data);
        System.out.println(found);

        ArrayList<Integer> path = nodeToRootPath(root, data);
        System.out.println(path);
    }

}

Time Complexity:

O(n) The time complexity for the function is linear as tree traversal is involved which is linear in terms of time complexity.

Space Complexity:

O(logn) The space complexity for the function is proportional to the height of the tree due to the recursion stack.