Given a binary tree and a integer value K, the task is to find all nodes in given binary tree having K leaves in subtree rooted with them.
Examples :
// For above binary tree
Input : k = 2
Output: {3}
// here node 3 have k = 2 leaves
Input : k = 1
Output: {6}
// here node 6 have k = 1 leave
Here any node having K leaves means sum of leaves in left subtree and in right subtree must be equal to K. So to solve this problem we use Postorder traversal of tree. First we calculate leaves in left subtree then in right subtree and if sum is equal to K, then print current node. In each recursive call we return sum of leaves of left subtree and right subtree to it’s ancestor.
Algorithm:
- start
- Set the base condition i.e if the node is null then return 0.
- Set the condition if left and right both child nodes are zero then return 1.
- Make a recursive call to find out the total child node of each node present in the tree.
- If the total child node of a specific node is equal to the given number then print the value of the node.
- End
Below is the implementation of above approach:
C++
// C++ program to count all nodes having k leaves // in subtree rooted with them #include<bits/stdc++.h> using namespace std; /* A binary tree node */struct Node { int data ; struct Node * left, * right ; }; /* Helper function 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 print all nodes having k leaves int kLeaves(struct Node *ptr,int k) { // Base Conditions : No leaves if (ptr == NULL) return 0; // if node is leaf if (ptr->left == NULL && ptr->right == NULL) return 1; // total leaves in subtree rooted with this // node int total = kLeaves(ptr->left, k) + kLeaves(ptr->right, k); // Print this node if total is k if (k == total) cout << ptr->data << " "; return total; } // Driver program to run the case int main() { struct Node *root = newNode(1); root->left = newNode(2); root->right = newNode(4); root->left->left = newNode(5); root->left->right = newNode(6); root->left->left->left = newNode(9); root->left->left->right = newNode(10); root->right->right = newNode(8); root->right->left = newNode(7); root->right->left->left = newNode(11); root->right->left->right = newNode(12); kLeaves(root, 2); return 0; } |
Java
// Java program to count all nodes having k leaves // in subtree rooted with them public class GfG { /* A binary tree node */static class Node { int data ; Node left, right ; Node(int data) { this.data = data; } Node() { } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return (node); } // Function to print all nodes having k leaves static int kLeaves(Node ptr,int k) { // Base Conditions : No leaves if (ptr == null) return 0; // if node is leaf if (ptr.left == null && ptr.right == null) return 1; // total leaves in subtree rooted with this // node int total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); // Print this node if total is k if (k == total) System.out.print(ptr.data + " "); return total; } // Driver program to run the case public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(4); root.left.left = newNode(5); root.left.right = newNode(6); root.left.left.left = newNode(9); root.left.left.right = newNode(10); root.right.right = newNode(8); root.right.left = newNode(7); root.right.left.left = newNode(11); root.right.left.right = newNode(12); kLeaves(root, 2); } } |
Python3
# Python3 program to count all nodes # having k leaves in subtree rooted with them # A binary tree node has data, pointer to # left child and a pointer to right child # Helper function that allocates a new node # with the given data and None left and # right pointers class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to print all nodes having k leaves def kLeaves(ptr, k): # Base Conditions : No leaves if (ptr == None): return 0 # if node is leaf if (ptr.left == None and ptr.right == None): return 1 # total leaves in subtree rooted with this # node total = kLeaves(ptr.left, k) + \ kLeaves(ptr.right, k) # Print this node if total is k if (k == total): print(ptr.data, end = " ") return total # Driver code root = newNode(1) root.left = newNode(2) root.right = newNode(4) root.left.left = newNode(5) root.left.right = newNode(6) root.left.left.left = newNode(9) root.left.left.right = newNode(10) root.right.right = newNode(8) root.right.left = newNode(7) root.right.left.left = newNode(11) root.right.left.right = newNode(12) kLeaves(root, 2) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to count all nodes having k leaves // in subtree rooted with them using System; class GfG { /* A binary tree node */public class Node { public int data ; public Node left, right ; public Node(int data) { this.data = data; } public Node() { } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return (node); } // Function to print all nodes having k leaves static int kLeaves(Node ptr,int k) { // Base Conditions : No leaves if (ptr == null) return 0; // if node is leaf if (ptr.left == null && ptr.right == null) return 1; // total leaves in subtree rooted with this // node int total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); // Print this node if total is k if (k == total) Console.Write(ptr.data + " "); return total; } // Driver program to run the case public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(4); root.left.left = newNode(5); root.left.right = newNode(6); root.left.left.left = newNode(9); root.left.left.right = newNode(10); root.right.right = newNode(8); root.right.left = newNode(7); root.right.left.left = newNode(11); root.right.left.right = newNode(12); kLeaves(root, 2); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to count all nodes having k leaves // in subtree rooted with them /* A binary tree node */class Node { /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ constructor(data) { this.data = data; this.left=this.right=null; } } // Function to print all nodes having k leaves function kLeaves(ptr,k) { // Base Conditions : No leaves if (ptr == null) return 0; // if node is leaf if (ptr.left == null && ptr.right == null) return 1; // total leaves in subtree rooted with this // node let total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); // Print this node if total is k if (k == total) document.write(ptr.data + " "); return total; } // Driver program to run the case let root = new Node(1); root.left = new Node(2); root.right = new Node(4); root.left.left = new Node(5); root.left.right = new Node(6); root.left.left.left = new Node(9); root.left.left.right = new Node(10); root.right.right = new Node(8); root.right.left = new Node(7); root.right.left.left = new Node(11); root.right.left.right = new Node(12); kLeaves(root, 2); // This code is contributed by rag2127 </script> |
Output
5 7
Time complexity : O(n) where n is the number of nodes in given tree.
Auxiliary Space: O(h) where h is the height of given Binary Tree due to Recursion.
This article is contributed by Shashank Mishra . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
