Count the unique type of nodes present in Binary tree

According to the property of a Binary tree, a node can have at most two children so there are three cases where a node can have two children, one child, or no child, the task is to track the count of unique nodes and return the total number of unique nodes that have no child, one child, and two children. Given the root of the binary tree return a vector where arr[0] represents the total unique nodes that contain 0 children, arr[1] represents the total unique nodes having 1 child, and arr[2] represents the total unique nodes that have exactly two children.

Examples:

Input:
2
/ \
1 4
/ \ \
2 1 1
/ \
7 5
Output: 4 1 2
Explanation: Nodes with no child are 2, 1, 7, and 5 and all these nodes have unique values so the count is 4. There is only 1 Node with 1 child i.e. 4 so the count will be 1 here.
Nodes with two children are 2 (root), 1 ( 2’s child ), and 1 ( 4’s child ), since 1 is repeating that’s why only 2 (root) and 1 will be counted as unique nodes so the count will be 2 here.
Input:
3
/ \
2 2
Output: 1 0 1
Explanation: Nodes with no child are 2 and 2 so the unique node’s count will be 1.
There is no node with 1 child so the count will be 0.
There is only 1 node with 2 children i.e. 3 (root node) so the count will be 1 here.

Approach: To solve the problem follow the below idea:

We can consider the different types of nodes as a pattern and use a hashmap to store every unique node’s pattern.

Follow the steps to solve the problem:

We can use three hashmaps for three patterns i.e. node with two children, node with one child, node with no child, and traverse over the tree and match the current node’s pattern if the current node’s value is unique then store it in the hashmap.
After completing the entire traversal return the size of all three hashmaps which represent all three patterns. For storing data in hashmaps pass the hashmap by reference.

Below code is the implementation of the above approach in C++:

// C++ program to count the unique

// nodes in Binary tree

#include <bits/stdc++.h>

using namespace std;

// A binary tree node has data,

// left child and right child

struct node {

int data;

node* left;

node* right;

};

// Helper function for inserting values in

// hashmap and tracking pattern

void trackPattern(node* root, map<int, int>& twoChild,

map<int, int>& oneChild,

map<int, int>& noChild)

{

// When node have two child

if (root->left && root->right) {

// Insert the node into

// hashmap

twoChild[root->data]++;

// Call recursion on left child

trackPattern(root->left, twoChild, oneChild,

noChild);

// Call recursion on right child

trackPattern(root->right, twoChild, oneChild,

noChild);

}

// When node is leaf node

else if (!root->left && !root->right) {

// Insert the node into

// hashmap

noChild[root->data]++;

}

// When node have one child

else {

oneChild[root->data]++;

// If right child is null then

// call recursion on left child

if (root->left)

trackPattern(root->left, twoChild, oneChild,

noChild);

// If left child is null then call

// recursion on right child

if (root->right)

trackPattern(root->right, twoChild, oneChild,

noChild);

}

// Main function for counting total unique nodes

vector<int> findUniquePattern(node* root)

{

// Initializing hashmap for tracking

// different patterns

map<int, int> twoChild, oneChild, noChild;

// Function call for tracking the

// unique nodes

trackPattern(root, twoChild, oneChild, noChild);

// Returning the size of hashmap which total

// represents unique nodes

return { (int)noChild.size(), (int)oneChild.size(),

(int)twoChild.size() };

}

// Helper function that allocates a new node

// with the given data and NULL left

// and right pointers.

node* newNode(int data)

{

node* node1 = new node();

node1->data = data;

node1->left = NULL;

node1->right = NULL;

return (node1);

}

// Driver code

int main()

{

node* root = newNode(2);

root->left = newNode(1);

root->right = newNode(4);

root->left->left = newNode(2);

root->left->right = newNode(1);

root->right->right = newNode(1);

root->right->right->left = newNode(7);

root->right->right->right = newNode(5);

// Function call

vector<int> uniqueNodes = findUniquePattern(root);

// Printing the values of unique

// nodes

cout << uniqueNodes[0] << " " << uniqueNodes[1] << " "

<< uniqueNodes[2];

return 0;

}

Output

4 1 2

Time Complexity: O(N*logN), N For traversing the tree and LogN for map operations
Auxiliary Space: O(N), For hashmaps, at max, N values can be stored

Count the unique type of nodes present in Binary tree

Count the unique type of nodes present in Binary tree

Recommend

Diagnosing nf_conntrack/nf_conntrack_count issues on CentOS mirrorlist nodes

Algo-Geeks: K distant nodes in a Binary Tree.

Using Negative Nodes to Count

Binary Tree Sum Of Nodes Using C++

Iterative method to Count full nodes in a Binary tree

Print extreme nodes of each level of Binary Tree in alternate order

Count leaf nodes in a Binary Tree (Recursive)

Create Binary Tree from given Array of relation between nodes

PROBLEM OF THE DAY: 01/09/2023 | Leftmost and rightmost nodes of binary tree

PROBLEM OF THE DAY: 10/10/2023 | Nodes at given distance in binary tree

About Joyk