Predecessor and Successor of an Element

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

110

O/P:

Predecessor = 80

Successor = 120

package pep.Day30;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

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

    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;
    }

    static Node predecessor, successor;
    static int state;

    private static void predecessorAndSuccessor(Node node, int data) {
        if (state == 0) {
            if (node.data == data)
                state = 1;
            else
                predecessor = node;
        } else if (state == 1) {
            successor = node;
            state = 2;
        }
        for (Node child : node.children) {
            predecessorAndSuccessor(child, data);
        }
    }

    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);
        predecessor = null;
        successor = null;
        state = 0;
        predecessorAndSuccessor(root, data);

        if (predecessor == null)
            System.out.println("Predecessor = Not found");
        else
            System.out.println("Predecessor = " + predecessor.data);


        if (successor == null)
            System.out.println("Successor = Not found");
        else
            System.out.println("Successor = " + successor.data);

    }


}

Time Complexity: O(n)

The time complexity of the above solution is O(n) as we are traversing all the nodes of the tree.

Space Complexity: O(1)

The space complexity of the above solution is O(1) as we have not used any extra memory. But, if we consider the recursion space then it is O(logn) as the max height of the recursion stack will be equal to height of the tree i.e. O(logn).