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

Count BST subtrees that lie in given range - GeeksforGeeks

Count BST subtrees that lie in given range - GeeksforGeeks
Given a Binary Search Tree (BST) of integer values and a range [low, high], return count of nodes where all the nodes under that node (or subtree rooted with that node) lie in the given range.

Input:
        10
      /    \
    5       50
   /       /  \
 1       40   100
Range: [5, 45]
Output:  1 
There is only 1 node whose subtree is in the given range.
The node is 40 

The idea is to traverse the given Binary Search Tree (BST) in bottom up manner. For every node, recur for its subtrees, if subtrees are in range and the nodes is also in range, then increment count and return true (to tell the parent about its status). Count is passed as a pointer so that it can be incremented across all function calls.

// A recursive function to get count of nodes whose subtree

// is in range from low to hgih.  This function returns true

// if nodes in subtree rooted under 'root' are in range.

bool getCountUtil(node *root, int low, int high, int *count)

{

    // Base case

    if (root == NULL)

       return true;

  // call inRange first, so if false, no need to check its subtree

    // Recur for left and right subtrees

    bool l = (root->left) ?  getCountUtil(root->left, low, high, count) : true;

    bool r = (root->right) ? getCountUtil(root->right, low, high, count) : true;

 

 

    // If both left and right subtrees are in range and current node

    // is also in range, then increment count and return true

    if (l && r && inRange(root, low, high))

    {

       ++*count;

       return true;

    }

 

    return false;

}

 

// A wrapper over getCountUtil(). This function initializes count as 0

//  and calls getCountUtil()

int getCount(node *root, int low, int high)

{

    int count = 0;

    getCountUtil(root, low, high, &count);

    return count;

}

bool inRange(node *root, int low, int high)

{

    return root->data >= low && root->data <= high;

}

http://code.geeksforgeeks.org/dOyzNK ???
Read full article from Count BST subtrees that lie in given range - GeeksforGeeks