Given a binary tree and an integer K, the task is to find the K smallest leaf nodes from the given binary tree. The number of leaf nodes will always be at least K.
Examples:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ \
21 8 19
Output: 6 8 19
Explanation:
There are 4 leaf nodes in the above binary tree
out of which 6, 8, 19 are the smallest three leaf nodes.Input:
11
/ \
12 3
/ \ / \
41 15 61 1
\
8
Output: 1 8 15
Explanation:
There are 4 leaf nodes in the above binary tree
out of which 1, 8, 15 are the smallest three leaf nodes.
Approach: Follow the steps below to solve the problem:
- Traverse the Binary Tree.
- Check for each node if it contains neither left child nor the right child. If found to be true, then that node is a leaf node. Store all such nodes in an array.
- Sort the array of leaf nodes and print the K smallest leaf values from the array.
Below is the implementation of the above approach:
C++
// C++ program of the// above approach#include <bits/stdc++.h>using namespace std;// Structure of// binary tree nodestruct Node { int data; Node *left, *right;};// Function to create new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Utility function which calculates// smallest three nodes of all leaf nodesvoid storeLeaf(Node* root, vector<int>& arr){ if (!root) return; // Check if current root is a leaf node if (!root->left and !root->right) { arr.push_back(root->data); return; } // Traverse the left // and right subtree storeLeaf(root->left, arr); storeLeaf(root->right, arr);}// Function to find the K smallest// nodes of the Binary Treevoid KSmallest(Node* root, int k){ vector<int> arr; storeLeaf(root, arr); // Sorting the Leaf nodes array sort(arr.begin(), arr.end()); // Loop to print the K smallest // Leaf nodes of the array for (int i = 0; i < k; i++) { if (i < arr.size()) { cout << arr[i] << " "; } else { break; } }}// Driver Codeint main(){ // Construct binary tree Node* root = newNode(1); root->left = newNode(2); root->left->left = newNode(4); root->left->left->left = newNode(21); root->left->right = newNode(5); root->left->right->right = newNode(8); root->right = newNode(3); root->right->left = newNode(6); root->right->right = newNode(7); root->right->right->right = newNode(19); // Function Call KSmallest(root, 3); return 0;} |
Java
// Java program of the// above approachimport java.util.*;class GFG{// Structure of// binary tree nodestatic class Node{ int data; Node left, right;};// Function to create new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Utility function which calculates// smallest three nodes of all leaf nodesstatic Vector<Integer> storeLeaf(Node root, Vector<Integer> arr){ if (root == null) return arr; // Check if current root is a leaf node if (root.left == null && root.right == null) { arr.add(root.data); return arr; } // Traverse the left // and right subtree arr = storeLeaf(root.left, arr); arr = storeLeaf(root.right, arr); return arr;}// Function to find the K smallest// nodes of the Binary Treestatic void KSmallest(Node root, int k){ Vector<Integer> arr = new Vector<Integer>(); arr = storeLeaf(root, arr); // Sorting the Leaf nodes array Collections.sort(arr); // Loop to print the K smallest // Leaf nodes of the array for(int i = 0; i < k; i++) { if (i < arr.size()) { System.out.print(arr.get(i) + " "); } else { break; } }}// Driver Codepublic static void main(String[] args){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.left.left = newNode(21); root.left.right = newNode(5); root.left.right.right = newNode(8); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(19); // Function call KSmallest(root, 3);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the # above approach# Binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Utility function which calculates# smallest three nodes of all leaf nodesdef storeLeaf(root: Node, arr : list) -> None: if (not root): return # Check if current root # is a leaf node if (not root.left and not root.right): arr.append(root.data) return # Traverse the left # and right subtree storeLeaf(root.left, arr) storeLeaf(root.right, arr)# Function to find the K smallest# nodes of the Binary Treedef KSmallest(root: Node, k: int) -> None: arr = [] storeLeaf(root, arr) # Sorting the Leaf # nodes array arr.sort() # Loop to print the K smallest # Leaf nodes of the array for i in range(k): if (i < len(arr)): print(arr[i], end = " ") else: break# Driver Codeif __name__ == "__main__": # Construct binary tree root = Node(1) root.left = Node(2) root.left.left = Node(4) root.left.left.left = Node(21) root.left.right = Node(5) root.left.right.right = Node(8) root.right = Node(3) root.right.left = Node(6) root.right.right = Node(7) root.right.right.right = Node(19) # Function Call KSmallest(root, 3)# This code is contributed by sanjeev2552 |
C#
// C# program of the// above approachusing System;using System.Collections.Generic;class GFG{// Structure of// binary tree nodeclass Node{ public int data; public Node left, right;};// Function to create new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Utility function which calculates// smallest three nodes of all leaf nodesstatic List<int> storeLeaf(Node root, List<int> arr){ if (root == null) return arr; // Check if current root is a leaf node if (root.left == null && root.right == null) { arr.Add(root.data); return arr; } // Traverse the left // and right subtree arr = storeLeaf(root.left, arr); arr = storeLeaf(root.right, arr); return arr;}// Function to find the K smallest// nodes of the Binary Treestatic void KSmallest(Node root, int k){ List<int> arr = new List<int>(); arr = storeLeaf(root, arr); // Sorting the Leaf nodes array arr.Sort(); // Loop to print the K smallest // Leaf nodes of the array for(int i = 0; i < k; i++) { if (i < arr.Count) { Console.Write(arr[i] + " "); } else { break; } }}// Driver Codepublic static void Main(String[] args){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.left.left = newNode(21); root.left.right = newNode(5); root.left.right.right = newNode(8); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(19); // Function call KSmallest(root, 3);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Structure of binary tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create new node function newNode(data) { let temp = new Node(data); return temp; } // Utility function which calculates // smallest three nodes of all leaf nodes function storeLeaf(root, arr) { if (root == null) return arr; // Check if current root is a leaf node if (root.left == null && root.right == null) { arr.push(root.data); return arr; } // Traverse the left // and right subtree arr = storeLeaf(root.left, arr); arr = storeLeaf(root.right, arr); return arr; } // Function to find the K smallest // nodes of the Binary Tree function KSmallest(root, k) { let arr = []; arr = storeLeaf(root, arr); // Sorting the Leaf nodes array arr.sort(function(a, b){return a - b}); // Loop to print the K smallest // Leaf nodes of the array for(let i = 0; i < k; i++) { if (i < arr.length) { document.write(arr[i] + " "); } else { break; } } } // Construct binary tree let root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.left.left = newNode(21); root.left.right = newNode(5); root.left.right.right = newNode(8); root.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(7); root.right.right.right = newNode(19); // Function call KSmallest(root, 3); </script> |
Output:
6 8 19
Time Complexity: O(N + L*logL), Here L is the count of leaf nodes and N is the number of nodes.
Auxiliary Space: O(L + logN)
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!
