zbir na pat vo drvo AIPS kolokvium

/*
Dadeno e binarno drvo i nekoj broj "suma". Potrebno e da se najde dali vo drvoto postoi pat megju bilo koi dva jazli, taka sto zbirot na
site jazli koi se vkluceni vo patot e ednakov na suma. Pocetniot jazel MORA da e roditel na krajniot jazel vo patot, znaci deka patot mora
da odi nadolu.
patot moze da se sostoi i samo od eden jazel.
* */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

}

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 class najdiZbirNaNodesEdnakovSoNekojBrVoBTree {


        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<Integer> nodes[] = new BNode[N];
            BTree<Integer> tree = new BTree<Integer>();

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

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

        System.out.println( hasPathSum( tree.root, suma ));

    }

    public static boolean hasPathSum(BNode root, int sum ) {

        if( root == null )
            return false;

        if ( hasPathSum(root,sum, 0) )
            return true;

        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }
    public static boolean hasPathSum(BNode root, int sum, int momentSum ){

        if( root == null )
            return false;
        if( (int)root.info + momentSum == sum )
            return true;

        return( hasPathSum( root.left, sum, (int)root.info + momentSum) ||
                hasPathSum( root.right, sum, (int)root.info + momentSum));
    }
}