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