Assume that each node in a binary tree represents a color. A clump is defined as 3 or more adjacent nodes with same color.
Write an algorithm to determine the number of clumps.
For example:
R
/ \
R R
/ \ / \
B B R G
/ \ / \
B B G G
\
G
The Above tree has 3 clumps:
4 Adjacent Reds starting at the root.
4 adjacent Greens in the right subtree.
3 adjacent Blues in the left subtree.
Answer:
Here is the solution in C++:
#include
using namespace std;
// The colors of the tree
enum Color
{
Unknown,
Red,
Green,
Blue
};
struct TreeNode
{
Color color;
TreeNode* left;
TreeNode* right;
TreeNode(Color c, TreeNode* _left=0, TreeNode* _right=0):
color(c), left(_left), right(_right){}
};
void CountClumps(TreeNode* node, Color parentColor, size_t &curCount, size_t &clumpCount)
{
if( node )
{
if (node->color != parentColor)
{
/* The color of the current node is not equal to the
* parent node's color, then we dont increase the curCount, but start a new
* clumpCount */
size_t _curCount = 1; // 1 because of the current node color
CountClumps(node->left, node->color, _curCount, clumpCount);
CountClumps(node->right, node->color, _curCount, clumpCount);
if ( _curCount >= 3 )
++clumpCount;
}
else
{
/* increase the curCount ( which signifies the nodes with same color )
* and let the parent decide about the clump, and traverse the left and
* right subtrees
* */
++curCount;
CountClumps(node->left, node->color, curCount, clumpCount);
CountClumps(node->right, node->color, curCount, clumpCount);
}
}
}
int main(int argc, char* argv[])
{
// The left subtree
TreeNode *n1 = new TreeNode(Green,0,0);
TreeNode *n2 = new TreeNode(Green,0,n1);
TreeNode *n3 = new TreeNode(Green,0,0);
TreeNode *n4 = new TreeNode(Green,n3,n2);
TreeNode *n5 = new TreeNode(Red,0,0);
TreeNode *n6 = new TreeNode(Red,n5,n4);
// The right subtree
TreeNode *n7 = new TreeNode(Blue, 0,0);
TreeNode *n8 = new TreeNode(Blue, 0,0);
TreeNode *n9 = new TreeNode(Blue, n7,n8);
TreeNode *n10 = new TreeNode(Blue, 0, 0);
TreeNode *n11 = new TreeNode(Blue, n10, n9);
// The Root
TreeNode *root = new TreeNode(Red, n11, n6);
size_t curCount = 0;
size_t clumpCount = 0;
CountClumps( root, Unknown, curCount, clumpCount );
cout << "Clumps " << clumpCount << endl;
// set the left subtree to null
curCount = 0;
clumpCount = 0;
root->left = 0;
CountClumps( root, Unknown, curCount, clumpCount );
cout << "Clumps " << clumpCount << endl;
// set the right subtree to null
curCount = 0;
clumpCount = 0;
root->right= 0;
root->left = n11;
CountClumps( root, Unknown, curCount, clumpCount );
cout << "Clumps " << clumpCount << endl;
// Sorry forgot to release the memory of the TreeNode :D
return clumpCount;
}
