Google Interview Question
Software Engineer / DevelopersCountry: United States
if((root->data == L_data) && (root->data == R_data))
{
temp = L_C + R_C + 1;
count += (L_C * R_C) + L_C + R_C+1;
}
this is for a sub tree with definition: A sub tree of a tree T is a tree consisting of a node in T and all of its descendants in T should be uni-value (en.wikipedia.org/wiki/Tree_data_structure)
int UniValueSubTrees(node *root, int &count)
{
if(!root)
return 0;
if(!root->left && !root->right)
{
count++;
return 0;
}
int L_C = UniValueSubTrees(root->left, count);
int R_C = UniValueSubTrees(root->right, count);
int 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)) || root->data == L_data || root->data == R_data)
{
if(L_C == 0 && R_C == 0)
{
count++;
return 0;
}
return 1;
}
else
return 1;
}
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);
}
}
}
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?
algos: are you sure about that explanation. I am not familiar with the "uni-value sub-trees" term but still I do not see why in your example you take 1,4,5 as a possible subtrees. Can we take just the root as a "subtree" and cut its leaves? I am asking since according to me a subtree is of a tree T is a tree consisting of a node in T and all of its descendants in T. So according this definition all possible subtrees in your example are 3 - No: 2,3,6. Please explain if I miss something?
a tree or sub-tree can have one or more than one node... sub tree can or can't have root node, it can be any where in the tree but should be linked to each other.
------------1
-------2--------3
----4----5 --6----7
lets consider all of the node values are equal to 10..
here few of the sub trees are
1. all single values
2. (1,2) (1,3) (2,4) (2,5) (3,6) (2,4,5)
3. but NOT (2,4,6) and (1,3,5)
Thanks for the answer @algo. I think you are wrong with the terminology of a subtree. Check en.wikipedia.org/wiki/Tree_(data_structure)#Terminology specially last parahraph (emphasize on "ALL of its descendants in T."). So you cannot say that (2,4) is a subtree of the example you gave. If you take 2 as the root of the subtree so the answer would be (2,4,5). Hope we are on the same line here.
en.wikipedia.org/wiki/Tree_data_structure
This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).
yes in a Graph definition of a subgraph (as a tree) is different and is as you did it. But here the idea is simply about the tree. Do you think the interviewer is meaning subGraph(if so he would probably ask the question in the context of a graph). That is why your solution is too complicated for this problem and if you not mention that we are talking about graphs it would be wrong. Otherwise it is an interesting approach but for different question.
thanks for the discussion and good luck :)
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; }
}
- algos October 01, 2012