[ADSx] - Distance In A Tree

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

class BNode<E> {

    public E info;
    public BNode<E> left;
    public BNode<E> right;

    static int LEFT = 1;
    static int RIGHT = 2;

    public BNode(E info) {
        this.info = info;
        left = null;
        right = null;
    }

    public BNode() {
        this.info = null;
        left = null;
        right = null;
    }

    public BNode(E info, BNode<E> left, BNode<E> right) {
        this.info = info;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "" + info;
    }
}

class BTree<E> {

    public BNode<E> root;

    public BTree() {
        root = null;
    }

    public BTree(E info) {
        root = new BNode<E>(info);
    }

    public void makeRootNode(BNode<E> node) {
        root = node;
    }

    public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {

        if (where == BNode.LEFT) {
            if (node.left != null)  // veke postoi element
                return null;
            node.left = tmp;
        } else {
            if (node.right != null) // veke postoi element
                return null;
            node.right = tmp;
        }

        return tmp;
    }

    public void inOrder(BNode<E> node) {
        if (node == null) return;
        if (node.left != null) inOrder(node.left);
        System.out.print(node.info.toString() + " ");
        if (node.right != null) inOrder(node.right);
    }

    public void levelOrderQueue(BNode<E> node) {
        Queue<BNode<E>> queue = new ArrayDeque<>();
        int levelNodes = 0;
        if (node == null) return;
        queue.add(node);
        while (!queue.isEmpty()) {
            levelNodes = queue.size();
            while (levelNodes > 0) {
                BNode<E> poll = queue.poll();
                System.out.print(" " + poll.info.toString());
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                levelNodes--;
            }
            System.out.print(System.lineSeparator());
        }
    }

    public BNode<E> findNodeByData(BNode<E> node, E info) {
        if (node == null) return null;
        if (node.info.equals(info)) return node;
        BNode<E> left = findNodeByData(node.left, info);
        return left == null ? findNodeByData(node.right, info) : left;
    }

    public BNode<E> LeastCommonAncestor(BNode<E> current, BNode<E> one, BNode<E> two) {
        if (current == null) return null;
        if (current == one || current == two) return current;
        BNode<E> left = LeastCommonAncestor(current.left, one, two);
        BNode<E> right = LeastCommonAncestor(current.right, one, two);
        if (left != null && right != null) return current;
        return left == null ? right : left;
    }

    public int depth(BNode<E> current, BNode<E> target) {
        if (current == null) return -1;
        if (current == target) return 0;
        int left = depth(current.left, target);
        int right = depth(current.right, target);
        if (left == -1 && right == -1) return -1;
        return left == -1 ? right + 1 : left + 1;
    }

    public int distanceBetween(BNode<E> root, BNode<E> one, BNode<E> two) {
        if (root == null || one == null || two == null) return -1;
        BNode<E> ancestor = LeastCommonAncestor(root, one, two);
        int depth1 = depth(root, ancestor);
        int depth2 = depth(root, one);
        int depth3 = depth(root, two);
        return depth2 + depth3 - 2 * depth1;
    }

    public void distanceBetweenByInfo(BNode<E> root, E infoOne, E infoTwo) {
        BNode<E> one = findNodeByData(root, infoOne);
        BNode<E> two = findNodeByData(root, infoTwo);
        int distanceBetween = distanceBetween(root, one, two);
        if (distanceBetween == -1) System.out.println("ERROR");
        else System.out.println(distanceBetween * 2);
    }
}

public class NodeDistance {

    public static void main(String[] args) throws Exception {
        int i, j, k;
        int index;
        String action;

        String line;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        BNode<String> nodes[] = new BNode[N];
        BTree<String> tree = new BTree<String>();

        for (i = 0; i < N; i++)
            nodes[i] = new BNode<String>();

        for (i = 0; i < N; i++) {
            line = br.readLine();
            st = new StringTokenizer(line);
            index = Integer.parseInt(st.nextToken());
            nodes[index].info = st.nextToken();
            action = st.nextToken();
            if (action.equals("LEFT")) {
                tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.LEFT, nodes[index]);
            } else if (action.equals("RIGHT")) {
                tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.RIGHT, nodes[index]);
            } else {
                // this node is the root
                tree.makeRootNode(nodes[index]);
            }
        }

        /*tree.inOrder(tree.root);
        System.out.println();
        tree.levelOrderQueue(tree.root);*/

        int cases = Integer.parseInt(br.readLine());
        for (int l = 0; l < cases; l++) {
            String split[] = br.readLine().split(" +");
            String from = split[0];
            String to = split[1];

            tree.distanceBetweenByInfo(tree.root, from, to);
        }
        br.close();


    }

}
/**
 * You are given a filled tree, where each edge has a weight of 2. For each pair of nodes,
 * find the shortest distance between them. If there is no solution, print "Error".
 * <p>
 * Name of the class (Java): NodeDistance.
 */



interface Stack<E> {

    // Elementi na stekot se objekti od proizvolen tip.

    // Metodi za pristap:

    public boolean isEmpty();
    // Vrakja true ako i samo ako stekot e prazen.

    public E peek();
    // Go vrakja elementot na vrvot od stekot.

    // Metodi za transformacija:

    public void clear();
    // Go prazni stekot.

    public void push(E x);
    // Go dodava x na vrvot na stekot.

    public E pop();
    // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
}

class ArrayStack<E> implements Stack<E> {
    private E[] elems;
    private int depth;

    @SuppressWarnings("unchecked")
    public ArrayStack(int maxDepth) {
        // Konstrukcija na nov, prazen stek.
        elems = (E[]) new Object[maxDepth];
        depth = 0;
    }


    public boolean isEmpty() {
        // Vrakja true ako i samo ako stekot e prazen.
        return (depth == 0);
    }


    public E peek() {
        // Go vrakja elementot na vrvot od stekot.
        if (depth == 0)
            throw new NoSuchElementException();
        return elems[depth - 1];
    }


    public void clear() {
        // Go prazni stekot.
        for (int i = 0; i < depth; i++) elems[i] = null;
        depth = 0;
    }


    public void push(E x) {
        // Go dodava x na vrvot na stekot.
        elems[depth++] = x;
    }


    public E pop() {
        // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
        if (depth == 0)
            throw new NoSuchElementException();
        E topmost = elems[--depth];
        elems[depth] = null;
        return topmost;
    }
}