NodeDistance.java

package zad4;

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 makeRoot(E elem) {
        root = new BNode(elem);
    }

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

    public BNode<E> addChild(BNode<E> node, int where, E elem) {

        BNode<E> tmp = new BNode<E>(elem);

        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 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 BNode<E> getNode(E x) {
        return getNode(this.root, x);
    }

    private BNode<E> getNode(BNode<E> r, E x) {

        //System.out.println(x);
        if (r == null) {
            return null;
        }
        if (r.info.equals(x.toString())) {
            return r;
        }

        BNode<E> a = getNode(r.left, x);
        BNode<E> b = getNode(r.right, x);

        if (a != null) {
            return a;
        } else {
            return b;
        }
    }

    public BNode<E> getParent(BNode<E> node) {
        return getParent(this.root, node);
    }

    private BNode<E> getParent(BNode<E> n, BNode<E> node) {

        if (n == null) {
            return null;
        }
        if (n.left == null && n.right == null) {
            return null;
        }

        if (n.left == node || n.right == node) {
            return n;
        }

        BNode<E> a = getParent(n.left, node);
        BNode<E> b = getParent(n.right, node);

        if (a != null) {
            return a;
        } else {
            return b;
        }

    }

    public int isUnder(BNode<E> node, BNode<E> gorno) {

        int l = 0;

        if (node == gorno) {
            return 0;
        }

        if (getParent(node) == gorno) {
            return 2;
        }

        while (node != gorno) {
            node = getParent(node);
            l += 2;

            if (node == this.root) {
                return -1;
            }
        }

        return l;
    }

    public BNode<E> findCommonRoot(BNode<E> n1, BNode<E> n2) {
        return findCommonRoot(this.root, n1, n2);
    }

    private BNode<E> findCommonRoot(BNode<E> root, BNode<E> n1, BNode<E> n2) {

        if (isUnder(n1, root.left) > 0 && isUnder(n2, root.left) > 0) {
            return findCommonRoot(root.left, n1, n2);
        } else if (isUnder(n1, root.right) > 0 && isUnder(n2, root.right) > 0) {
            return findCommonRoot(root.right, n1, n2);
        } else {
            return root;
        }

    }

}

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

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

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

            BNode<String> fromNode = tree.getNode(from);
            BNode<String> toNode = tree.getNode(to);

            if (fromNode == null || toNode == null) {
                System.out.println("ERROR");
                continue;
            }

            int x = tree.isUnder(fromNode, toNode);
            int y = tree.isUnder(toNode, fromNode);

            if (x > -1 || y > -1) {

                if (x > -1) {
                    System.out.println(x);
                } else {
                    System.out.println(y);
                }

            } else {

                BNode<String> cr = tree.findCommonRoot(fromNode, toNode);

                int z = tree.isUnder(fromNode, cr) + tree.isUnder(toNode, cr);
                System.out.println(z);

            }


        }
        br.close();

    }

}