Ceil And Floor 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

50

O/P:

Floor = 40

Ceil = 60

ceil   -> smallest among larger
floor  -> largest among smaller

Algorithm:

1. We will again follow the "traverse and change", traverse through all the nodes and if the data inside the node is greater than the input value, we will store the value inside the ceil. This will be a potential ceil value. Similarly, if the data inside the node is less than the input value, we will store it in the floor variable. This will also be a potential floor value.

2. If we find some other node where the value of the node is smaller than the current ceil value then we will change the ceil value to it. Similarly if we find any other node where the value is larger than the current floor value, we will store it in floor. 

3. This process will continue till we traverse the entire tree and then, we will print the values of the ceil and floor.

package pep.Day31;

import pep.Day30.Predecessor_and_Successor_of_Element;

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

public class Ceil_and_Floor_in_GenericTree {
    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;
    }

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

        ceil = Integer.MAX_VALUE;
        floor = Integer.MIN_VALUE;

        ceilAndFloor(root, data);

        System.out.println("Floor = " + floor);
        System.out.println("Ceil = " + ceil);

    }

    // ceil  -> smallest among larger
    // floor  -> largest among smaller
    static int ceil, floor;

    private static void ceilAndFloor(Node node, int data) {
        if (node.data > data) {
            int potencialCeil = node.data;
            ceil = Math.min(potencialCeil, ceil);
        }

        if (node.data < data) {
            int potencialFloor = node.data;
            floor = Math.max(potencialFloor, floor);
        }

        for (Node child : node.children) {
            ceilAndFloor(child, data);
        }
    }

}

Time Complexity

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

Space Complexity

The space complexity of this solution is O(1). Again like almost every previous question, if we consider the recursion space the time complexity becomes O(logn) as the maximum height of the stack can be equal to the height of the tree i.e. O(logn).