Distance Between Two Nodes In A 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 110

O/P: 5

1• Calculate node to root path for both the nodes.

2• Keep iterating from the end and the last equal items in the path of both the nodes becomes the LCA.

3• Now the distance between two nodes will be the distance of node 1 from LCA in addition to the distance of node 2 from LCA.

package pep.Day29;

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

public class Distance_Between_Two_Nodes_In_GenericTree {

    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 int distanceBetweenNodes(Node node, int d1, int d2) {
        ArrayList<Integer> p1 = nodeToRootPath(node, d1);
        ArrayList<Integer> p2 = nodeToRootPath(node, d2);
        int i = p1.size() - 1, j = p2.size() - 1;
        while (i >= 0 && j >= 0 && p1.get(i) == p2.get(j)) {
            i--;
            j--;
        }
        i++;
        j--;
        return i + j;
    }

    private static ArrayList<Integer> nodeToRootPath(Node node, int data) {
        if (node.data == data) {
            ArrayList<Integer> base = new ArrayList<>();
            base.add(data);
            return base;
        }

        for (Node child : node.children) {
            ArrayList<Integer> path = nodeToRootPath(child, data);
            if (path.size() > 0) {
                path.add(child.data);
                return path;
            }
        }
        return new ArrayList<>();
    }


    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 d1 = Integer.parseInt(br.readLine());
        int d2 = Integer.parseInt(br.readLine());

        Node root = construct(arr);
        int lca = distanceBetweenNodes(root, d1, d2);
        System.out.println(lca);
        // display(root);
    }

}

Time Complexity: O(n): Finding the node in the entire tree to get the node to the root path takes O(n). Then, just traversing the node-to-root path (arrays) takes O(d) where d = depth of the node. In the worst case, d can be equal to n, hence total time complexity will be O(n) only.

Space Complexity: O(n) We are storing the node to the root path so the total auxiliary size is O(n).