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 5Output: 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 2Output: 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:
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; } |
Java
import java.util.*; class Node { int data; Node left; Node right; Node( int data) { this .data = data; left = null ; right = null ; } } public class Main { public static void main(String[] args) { Node root = new Node( 2 ); root.left = new Node( 1 ); root.right = new Node( 4 ); root.left.left = new Node( 2 ); root.left.right = new Node( 1 ); root.right.right = new Node( 1 ); root.right.right.left = new Node( 7 ); root.right.right.right = new Node( 5 ); // Function call List<Integer> uniqueNodes = findUniquePattern(root); // Printing the values of unique nodes System.out.println(uniqueNodes.get( 0 ) + " " + uniqueNodes.get( 1 ) + " " + uniqueNodes.get( 2 )); } // Function for counting total unique nodes public static List<Integer> findUniquePattern(Node root) { // Initializing hashmaps for tracking different patterns Map<Integer, Integer> twoChild = new HashMap<>(); Map<Integer, Integer> oneChild = new HashMap<>(); Map<Integer, Integer> noChild = new HashMap<>(); // Function call for tracking the unique nodes trackPattern(root, twoChild, oneChild, noChild); // Returning the size of hashmaps, which represents unique nodes return Arrays.asList(noChild.size(), oneChild.size(), twoChild.size()); } // Helper function for inserting values in hashmaps and tracking pattern public static void trackPattern(Node root, Map<Integer, Integer> twoChild, Map<Integer, Integer> oneChild, Map<Integer, Integer> noChild) { if (root == null ) { return ; } // When node have two child if (root.left != null && root.right != null ) { // Insert the node into hashmap twoChild.put(root.data, twoChild.getOrDefault(root.data, 0 ) + 1 ); // 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 == null && root.right == null ) { // Insert the node into hashmap noChild.put(root.data, noChild.getOrDefault(root.data, 0 ) + 1 ); } // When node have one child else { oneChild.put(root.data, oneChild.getOrDefault(root.data, 0 ) + 1 ); // If right child is not null, call recursion on right child if (root.left != null ) { trackPattern(root.left, twoChild, oneChild, noChild); } // If left child is not null, call recursion on left child if (root.right != null ) { trackPattern(root.right, twoChild, oneChild, noChild); } } } } |
Python3
# Node class class Node: # Constructor to initialize data def __init__( self , data): self .data = data self .left = None self .right = None # Function for counting total unique nodes def findUniquePattern(root): # Initializing hashmaps for tracking different patterns twoChild = {} oneChild = {} noChild = {} # Function call for tracking the unique nodes trackPattern(root, twoChild, oneChild, noChild) # Returning the size of hashmaps, which represents unique nodes return [ len (noChild), len (oneChild), len (twoChild)] # Helper function for inserting values in hashmaps and tracking pattern def trackPattern(root, twoChild, oneChild, noChild): if root is None : return # When node have two child if root.left is not None and root.right is not None : # Insert the node into hashmap twoChild[root.data] = twoChild.get(root.data, 0 ) + 1 # 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 elif root.left is None and root.right is None : # Insert the node into hashmap noChild[root.data] = noChild.get(root.data, 0 ) + 1 # When node have one child else : oneChild[root.data] = oneChild.get(root.data, 0 ) + 1 # If right child is not None, call recursion on right child if root.left is not None : trackPattern(root.left, twoChild, oneChild, noChild) # If left child is not None, call recursion on left child if root.right is not None : trackPattern(root.right, twoChild, oneChild, noChild) # Driver code if __name__ = = '__main__' : root = Node( 2 ) root.left = Node( 1 ) root.right = Node( 4 ) root.left.left = Node( 2 ) root.left.right = Node( 1 ) root.right.right = Node( 1 ) root.right.right.left = Node( 7 ) root.right.right.right = Node( 5 ) # Function call uniqueNodes = findUniquePattern(root) # Printing the values of unique nodes print (uniqueNodes[ 0 ], uniqueNodes[ 1 ], uniqueNodes[ 2 ]) |
C#
using System; using System.Collections.Generic; class Node { public int Data; public Node Left, Right; // Constructor to create a new node public Node( int item) { Data = item; Left = Right = null ; } } class GFG { // Helper function for the inserting values in the hashmap and tracking patterns private static void TrackPattern(Node root, Dictionary< int , int > twoChild, Dictionary< int , int > oneChild, Dictionary< int , int > noChild) { if (root == null ) return ; // When the node has two children if (root.Left != null && root.Right != null ) { twoChild[root.Data] = twoChild.ContainsKey(root.Data) ? twoChild[root.Data] + 1 : 1; TrackPattern(root.Left, twoChild, oneChild, noChild); TrackPattern(root.Right, twoChild, oneChild, noChild); } // When the node is a leaf node else if (root.Left == null && root.Right == null ) { noChild[root.Data] = noChild.ContainsKey(root.Data) ? noChild[root.Data] + 1 : 1; } // When the node has one child else { // Insert the node into the hashmap oneChild[root.Data] = oneChild.ContainsKey(root.Data) ? oneChild[root.Data] + 1 : 1; if (root.Left != null ) TrackPattern(root.Left, twoChild, oneChild, noChild); if (root.Right != null ) TrackPattern(root.Right, twoChild, oneChild, noChild); } } private static List< int > FindUniquePattern(Node root) { // Initializing hashmap for tracking // different patterns Dictionary< int , int > twoChild = new Dictionary< int , int >(); Dictionary< int , int > oneChild = new Dictionary< int , int >(); Dictionary< int , int > noChild = new Dictionary< int , int >(); TrackPattern(root, twoChild, oneChild, noChild); return new List< int > { noChild.Count, oneChild.Count, twoChild.Count }; } public static void Main( string [] args) { // Driver code Node root = new Node(2); root.Left = new Node(1); root.Right = new Node(4); root.Left.Left = new Node(2); root.Left.Right = new Node(1); root.Right.Right = new Node(1); root.Right.Right.Left = new Node(7); root.Right.Right.Right = new Node(5); List< int > uniqueNodes = FindUniquePattern(root); // Printing the values of unique nodes Console.WriteLine($ "{uniqueNodes[0]} {uniqueNodes[1]} {uniqueNodes[2]}" ); } } |
Javascript
// Define a binary tree node structure class TreeNode { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function to count unique nodes in a binary tree function findUniquePattern(root) { const noChild = new Map(); // To store nodes with no children const oneChild = new Map(); // To store nodes with one child const twoChild = new Map(); // To store nodes with two children // Helper function for inserting values in maps and tracking pattern function trackPattern(node) { if (!node) { return ; } // When the node has two children if (node.left && node.right) { // Insert the node into the twoChild map if (!twoChild.has(node.data)) { twoChild.set(node.data, 0); } twoChild.set(node.data, twoChild.get(node.data) + 1); // Recursively call on left child trackPattern(node.left); // Recursively call on right child trackPattern(node.right); } // When the node is a leaf node else if (!node.left && !node.right) { // Insert the node into the noChild map if (!noChild.has(node.data)) { noChild.set(node.data, 0); } noChild.set(node.data, noChild.get(node.data) + 1); } // When the node has one child else { // Insert the node into the oneChild map if (!oneChild.has(node.data)) { oneChild.set(node.data, 0); } oneChild.set(node.data, oneChild.get(node.data) + 1); // If the right child is not null, call recursively on it if (node.left) { trackPattern(node.left); } // If the left child is not null, call recursively on it if (node.right) { trackPattern(node.right); } } } // Start tracking unique nodes from the root trackPattern(root); // Return the counts of unique nodes in an array return [noChild.size, oneChild.size, twoChild.size]; } // Create the binary tree const root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(4); root.left.left = new TreeNode(2); root.left.right = new TreeNode(1); root.right.right = new TreeNode(1); root.right.right.left = new TreeNode(7); root.right.right.right = new TreeNode(5); // Function call const uniqueNodes = findUniquePattern(root); // Print the values of unique nodes console.log(uniqueNodes[0] + " " + uniqueNodes[1] + " " + uniqueNodes[2]); |
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
Contact Us