CareerCup

this is for a sub tree / sub graph with definition: A sub tree/sub graph of a tree T is a tree consisting of a node in T with zero or more of its descendants in T can be uni-value (en.wikipedia.org/wiki/Tree_data_structure)
    
there are 3 cases for this one, and for each case find number of uni-value sub trees and number of nodes that are equal to root node
 
1. for a given root, left data and right data is equal to root data then
     a. number of uni-value nodes are left_count+right_count+1
     b. number of sub trees are left_count*right_count + left_count + right_count + 1
 
2. for a given root, only left data is equal to root data then
     a. number of uni-value nodes are left_count + 1
     b. number of sub trees are left_count + 1
 
3. for a given root, only right data is equal to root data then
     a. number of uni-value nodes are right_count + 1
     b. number of sub trees are right_count + 1
 
int UniValueSubTrees(node *root, int &count)
{
    if(!root)
        return 0;
    
    int L_C = UniValueSubTrees(root->left, count);
    int R_C = UniValueSubTrees(root->right, count);
    
    int temp = 1, L_data=0, R_data=0;
    
    if(root->left)
        L_data = root->left->data;
    if(root->right)
        R_data = root->right->data;
    
    if((root->data == L_data) && (root->data == R_data))
    {
        temp = L_C + R_C + (L_C * R_C) + 1;
        count +=  temp;
    }
    else if(root->data == L_data)
    {
        temp = L_C + 1;
        count += temp;
    }
    else if(root->data == R_data)
    {
        temp = R_C + 1;
        count += temp;
    }
    else
        count += temp;
        
    return temp;
}
//function is called with count = 0 and finally count will have the number of uni-value sub trees

enum ResultType = {NULL, MIXED, EQUAL};
struct Result {
    ResultType type;
    int value;
    int count;
}

Result univalue( BST tree ) {
    if (tree == null) {
        return new Result( NULL, 0, 0 );
    }
    Result leftResult = univalue( tree.left );
    Result rightResult = univalue( tree.right );
    if ((leftResult.type == NULL || (leftResult.type == EQUAL && leftResult.value == tree.value))
        &&
        (rightResult.type == NULL || (rightResult.type == EQUAL && rightResult.value == tree.value))) {

        return new Result( EQUAL, tree.value, rightResult.count + leftResult.count + 1);
    } else {
        return new Result( MIXED, 0, rightResult.count + leftResult.count + 1);
    }
}

}

what is a uni - value subtree?
is that a leaf node?

Uni-value tree is a tree where the value of all the nodes is same.

I'm interpreting the question like this:
If the sub-tree from root->left has the same value for all nodes and the subtree from root->right has the same value for all nodes under it, then if the root->val == root->left->val == root->right->val, then the total number of uni-val sub trees is 1 since root and root->left and root->right comprise the uber sub tree. In other words, if all the nodes in a given tree have the same value, then the number of uni-val subtrees is 1 (irrespective of how many nodes are in the tree).
If however the value in root->val != root->left->val != root->right->val, then the number of uni-val subtrees are C1 + C2 (where C1 is the number of sub trees in left subtree and C2 is the number of subtrees in the right subtree.

Is this interpretation correct?

The question did not say binary tree. So treat it as a generic tree where the number of children can vary. Here is sample java code

public static int count(TreeNode root) {
        if (root == null) {
            return 0;
        }   

        if (root.getChildren().isEmpty()) {
            return 1;
        }   

        int num = 0;
        boolean uniValue = true;
        for (TreeNode sub : root.getChildren()) {
            if (sub.getValue() != root.getValue()) {
                uniValue = false;
            }   
            num += count(sub);
        }   

        if (!uniValue()) {
            return num + 1;
        } else {
            return 1;
        }   
    }

It takes O(n) time where n is the number of nodes on the tree since each node will be accessed only once.

//Call this method with root and one dummy node
private static int countUnivalueSubTrees(TreeNode root, TreeNode parent)
{
if (root != null)
{
int count = countUnivalueSubTrees(root.getLeft(), root)
+ countUnivalueSubTrees(root.getRight(), root);
if (root.getInfo() == parent.getInfo())
{
return count;
}
return 1 + count;

}
return 0;
}

Fully working Code in java :::

Time Complexity :: O(n) Bottom Up Approach
Space Complexity :: O(1) not considering recursion stack space

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author nikhil.agrawal
 */
public class UnivaluedSubTree {
    
    public static void main(String[] args) {

        TreeNode root = new TreeNode(2);
        TreeNode r2 = new TreeNode(2);
        TreeNode r3 = new TreeNode(2);
        TreeNode r4 = new TreeNode(3);
        TreeNode r5 = new TreeNode(3);
        TreeNode r6 = new TreeNode(3);
        TreeNode r7 = new TreeNode(3);
        
        root.left=r2;
        root.right=r3;
        
        r2.left=r4;
        r2.right=r5;
        r3.left=r6;
        r3.right=r7;
        
        
        countingUnivaluedTree(root);
        
    }
    
    
    static int count =0;
    
    static void countingUnivaluedTree(TreeNode root)
    {
        
        countingUnivaluedTreeUtil(root);
        
        System.out.println("Number of univalued trees :: " + count);
    }
    
    
    static boolean  countingUnivaluedTreeUtil(TreeNode r )
    {
        
        if(r==null) return true;
        
        boolean lB = countingUnivaluedTreeUtil(r.left);
        boolean rB = countingUnivaluedTreeUtil(r.right);
        
        if(lB && rB && (r.left==null || r.val==r.left.val) && (r.right==null || r.val==r.right.val))
        {
            count++;
            return true;
        }
        
        return false;
        
    }
    
    
    
    


}


class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) { val = x; }
}