[ADSx] - Grandfather-nephew Relations

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

class BNode<E> {

    public E info;
    public BNode<E> left;
    public BNode<E> right;
    char ltag;
    char rtag;
    static int LEFT = 1;
    static int RIGHT = 2;

    public BNode(E info) {
        this.info = info;
        left = null;
        right = null;
        ltag = '-';
        rtag = '-';
    }
}

class BTree<E> {

    public BNode<E> head;

    public BTree() {
        head = new BNode<E>(null);
        // po definicija ako nema koren, t.e. ako stebloto e prazno
        head.left = head;
        head.ltag = '-';
        // kaj vodacot sekogas desnata vrska pokazuva kon samiot sebe
        head.right = head;
        head.rtag = '+';
    }

    public BNode<E> makeRoot(E elem) {
        BNode<E> tmp = new BNode<E>(elem);
        head.left = tmp;
        head.ltag = '+';

        tmp.left = head;
        tmp.ltag = '-';
        tmp.right = head;
        tmp.rtag = '-';

        return tmp;
    }

    public BNode<E> makeRootNode(BNode<E> tmp) {
        head.left = tmp;
        head.ltag = '+';

        tmp.left = head;
        tmp.ltag = '-';
        tmp.right = head;
        tmp.rtag = '-';

        return tmp;
    }

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

        if (where == BNode.LEFT) {

            if (node.ltag == '+') // veke postoi element
            {
                return null;
            }

            tmp.left = node.left;
            tmp.ltag = '-';
            tmp.right = node;
            tmp.rtag = '-';
            node.left = tmp;
            node.ltag = '+';
        } else {

            if (node.rtag == '+') // veke postoi element
            {
                return null;
            }

            tmp.right = node.right;
            tmp.rtag = '-';
            tmp.left = node;
            tmp.ltag = '-';
            node.right = tmp;
            node.rtag = '+';
        }

        return tmp;
    }

    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);
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                levelNodes--;
            }
            System.out.print(System.lineSeparator());
        }
    }

    public void inorderNonRecursive() {

        if (head.ltag == '-')      // drvoto e prazno
            return;

        System.out.print("INORDER (nonrecursive): ");

        BNode<E> p = head.left;

        while (p.ltag == '+')
            p = p.left;

        while (p != head) {
            System.out.print(p.info.toString() + " ");
            p = successorInorder(p);
        }
        System.out.println();

    }

    public void inorder() {
        System.out.print("INORDER: ");

        if (head.ltag == '+')
            inorderR(head.left);

        System.out.println();
    }

    void inorderR(BNode<E> n) {

        if (n.ltag == '+')
            inorderR(n.left);

        System.out.print(n.info.toString() + " ");

        if (n.rtag == '+')
            inorderR(n.right);

    }

    public BNode<E> insertRight(BNode<E> parent, E info) {

        BNode<E> child = new BNode<E>(info);

        child.ltag = '-';
        child.left = parent;
        child.rtag = parent.rtag;
        child.right = parent.right;

        parent.right = child;
        parent.rtag = '+';

        if (child.rtag == '+') {
            BNode<E> temp = child.right;
            while (temp.ltag == '+') {
                temp = temp.left;
            }
            temp.left = child;
        }

        return child;
    }

    public BNode<E> predecessorInorder(BNode<E> node) {

        if (node.ltag == '-') {
            return node.left;
        }

        BNode<E> p = node.left;
        while (p.rtag == '+') {
            p = p.right;
        }

        return p;
    }

    public BNode<E> successorInorder(BNode<E> node) {

        if (node.rtag == '-') {
            return node.right;
        }

        BNode<E> p = node.right;
        while (p.ltag == '+') {
            p = p.left;
        }

        return p;
    }

    public int getNumberOfRelations() {
        /**
         * Tags are used as a boolean for existence
         */
        int sum = 0;
        BNode<E> current = head;
        // Go maximally to the left
        while (current.ltag == '+') {
            current = current.left;
        }
        //System.out.println(current.info);
        while (current != head) {
            if (current.ltag == '+') {
                if (current.left.ltag == '+') {
                    sum++;
                }
                if (current.left.rtag == '+') {
                    sum++;
                }
            }
            if (current.rtag == '+') {
                if (current.right.ltag == '+') {
                    sum++;
                }
                if (current.right.rtag == '+') {
                    sum++;
                }
            }
            //System.out.println(current.info + " S: " + sum);
            current = successorInorder(current);
        }
        return sum;
    }
}

public class Relations {

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

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

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

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

        for (i = 0; i < N; i++) {
            nodes[i] = null;
        }

        for (i = 0; i < N; i++) {
            String line = br.readLine();
            st = new StringTokenizer(line);
            int index = Integer.parseInt(st.nextToken());
            nodes[index] = new BNode<Integer>(Integer.parseInt(st.nextToken()));
            String 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]);
            }
        }

        br.close();

        System.out.println(tree.getNumberOfRelations());

    }
}
/**
 * You are given a binary tree.
 * You need to find the number of grandfather-nephew relations.
 * Grandfather-nephew relations exists,
 * if one of the children of A, is a parent to B.
 * Recursion is not allowed.
 */