Find Count of Single Valued Subtrees - GeeksforGeeks

Find Count of Single Valued Subtrees - GeeksforGeeks
Given a binary tree, write a program to count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value. Expected time complexity is O(n).

A Simple Solution is to traverse the tree. For every traversed node, check if all values under this node are same or not. If same, then increment count. Time complexity of this solution is O(n2).

An Efficient Solution is to traverse the tree in bottom up manner. For every subtree visited, return true if subtree rooted under it is single valued and increment count. So the idea is to use count as a reference parameter in recursive calls and use returned values to find out if left and right subtrees are single valued or not.

// This function increments count by number of single

// valued subtrees under root. It returns true if subtree

// under root is Singly, else false.

bool countSingleRec(Node* root, int &count)

{

    // Return false to indicate NULL

    if (root == NULL)

       return true;

 

    // Recursively count in left and right subtrees also

    bool left = countSingleRec(root->left, count);

    bool right = countSingleRec(root->right, count);

 

    // If any of the subtrees is not singly, then this

    // cannot be singly.

    if (left == false || right == false)

       return false;

 

    // If left subtree is singly and non-empty, but data

    // doesn't match

    if (root->left && root->data != root->left->data)

        return false;

 

    // Same for right subtree

    if (root->right && root->data != root->right->data)

        return false;

 

    // If none of the above conditions is true, then

    // tree rooted under root is single valued, increment

    // count and return true.

    count++;

    return true;

}

Read full article from Find Count of Single Valued Subtrees - GeeksforGeeks