Unival

CountUnival

package org.idey.algo.datastructure.tree;

public class CountUniValTree<E> {
    private TreeNode<E> root;
    public CountUniValTree(TreeNode<E> root) {
        this.root = root;
    }

    private boolean countSingleRec(TreeNode<E> root, Counter c) {
        // Return false to indicate NULL
        if (root == null) {
            return true;
        }

        // Recursively count in left and right subtrees also
        boolean left = countSingleRec(root.getLeft(), c);
        boolean right = countSingleRec(root.getRight(), c);

        // If any of the subtrees is not singly, then this
        // cannot be singly.
        if (!left || !right) {
            return false;
        }

        // If left subtree is singly and non-empty, but data
        // doesn't match
        if (root.getLeft() != null && !root.equals(root.getLeft())) {
            return false;
        }

        // Same for right subtree
        if (root.getRight() != null && !root.equals(root.getRight())) {
            return false;

        }

        // If none of the above conditions is true, then
        // tree rooted under root is single valued, increment
        // count and return true.
        c.cout++;
        return true;

    }

    private class Counter{
        private int cout=0;
    }

    public int countUnival(){
        Counter c = new Counter();
        countSingleRec(root,c);
        return c.cout;
    }


    public static void main(String[] args){
        TreeNode<Integer> A = new TreeNode<>(1);
        TreeNode<Integer> B = new TreeNode<>(2);
        TreeNode<Integer> C = new TreeNode<>(3);
        TreeNode<Integer> D = new TreeNode<>(4);
        TreeNode<Integer> E = new TreeNode<>(5);

        TreeNode<Integer> F = new TreeNode<>(6);
        TreeNode<Integer> G = new TreeNode<>(7);

        D.addLeft(F).addRight(G);
        C.addLeft(D).addRight(E);
        A.addLeft(B).addRight(C);

        CountUniValTree<Integer> countUniValTree = new CountUniValTree<>(A);
        System.out.println(countUniValTree.countUnival());
    }

}