Tutorialspoint.dev

Root to leaf paths having equal lengths in a Binary Tree

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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter