Given a binary tree, print the number of root to leaf paths having equal lengths.
Examples:
Input : Root of below tree 10 / 8 2 / / 3 5 2 4 Output : 4 paths are of length 3. Input : Root of below tree 10 / 8 2 / / 3 5 2 4 / 9 1 Output : 2 paths are of length 3 2 paths are of length 4
The idea is to traverse the tree and keep track of path length. Whenever we reach a leaf node, we increment path length count in a hash map.
Once we have traverse the tree, hash map has counts of distinct path lengths. Finally we print contents of hash map.
C++
// C++ program to count root to leaf paths of different // lengths. #include<bits/stdc++.h> using namespace std; /* A binary tree node */ struct Node { int data; struct Node* left, *right; }; /* utility that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newnode( int data) { struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } // Function to store counts of different root to leaf // path lengths in hash map m. void pathCountUtil(Node *node, unordered_map< int , int > &m, int path_len) { // Base condition if (node == NULL) return ; // If leaf node reached, increment count of path // length of this root to leaf path. if (node->left == NULL && node->right == NULL) { m[path_len]++; return ; } // Recursively call for left and right subtrees with // path lengths more than 1. pathCountUtil(node->left, m, path_len+1); pathCountUtil(node->right, m, path_len+1); } // A wrapper over pathCountUtil() void pathCounts(Node *root) { // create an empty hash table unordered_map< int , int > m; // Recursively check in left and right subtrees. pathCountUtil(root, m, 1); // Print all path lenghts and their counts. for ( auto itr=m.begin(); itr != m.end(); itr++) cout << itr->second << " paths have length " << itr->first << endl; } // Driver program to run the case int main() { struct Node *root = newnode(8); root->left = newnode(5); root->right = newnode(4); root->left->left = newnode(9); root->left->right = newnode(7); root->right->right = newnode(11); root->right->right->left = newnode(3); pathCounts(root); return 0; } |
Python3
# Python3 program to count root to leaf # paths of different lengths. # Binary Tree Node """ utility that allocates a newNode with the given key """ class newnode: # Construct to create a newNode def __init__( self , key): self .key = key self .left = None self .right = None # Function to store counts of different # root to leaf path lengths in hash map m. def pathCountUtil(node, m,path_len) : # Base condition if (node = = None ) : return # If leaf node reached, increment count of # path length of this root to leaf path. if (node.left = = None and node.right = = None ): if path_len[ 0 ] not in m: m[path_len[ 0 ]] = 0 m[path_len[ 0 ]] + = 1 return # Recursively call for left and right # subtrees with path lengths more than 1. pathCountUtil(node.left, m, [path_len[ 0 ] + 1 ]) pathCountUtil(node.right, m, [path_len[ 0 ] + 1 ]) # A wrapper over pathCountUtil() def pathCounts(root) : # create an empty hash table m = {} path_len = [ 1 ] # Recursively check in left and right subtrees. pathCountUtil(root, m, path_len) # Print all path lenghts and their counts. for itr in sorted (m, reverse = True ): print (m[itr], " paths have length " , itr) # Driver Code if __name__ = = '__main__' : root = newnode( 8 ) root.left = newnode( 5 ) root.right = newnode( 4 ) root.left.left = newnode( 9 ) root.left.right = newnode( 7 ) root.right.right = newnode( 11 ) root.right.right.left = newnode( 3 ) pathCounts(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
Output:
1 paths have length 4 2 paths have length 3
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments