Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Test Case
3.
Approach
3.1.
Steps of algorithm
3.2.
C++ Code
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
How to count the number of leaf nodes in a binary tree?
4.3.
What is the preorder traversal of a tree?
4.4.
How to find the number of leaf nodes in a Perfect Binary Tree?
5.
Conclusion
Last Updated: Mar 27, 2024

Find K Smallest Leaf Nodes from a given Binary Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this question, we are given a binary tree and an integer K as input. We will have to print the K smallest leaf nodes present in the tree. The given input tree must contain at least K leaf nodes.

Also see, Data Structures

Problem Statement

Find K smallest leaf nodes from a given Binary Tree

Test Case

Let us take a few sample test cases to understand the question better.

Test Case 1

Tree

Input: K = 3

Output: 5, 6, 7

As we can see, the above tree has four leaf nodes: 

8, 5, 6, and 7 (from left to right).

Among these four leaf nodes, the three smallest nodes are clearly 5, 6, and 7.

Test Case 2

Tree

Input: K = 6

Output: 10, 11, 12, 13, 48, 76

The above tree has six leaf nodes:

 12, 48, 76, 13, 10 and 11 (from left to right).

Among these six leaf nodes, the six smallest nodes are 10, 11, 12, 13, 48, and 76.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

Before finding the K smallest leaf nodes, we must find all the leaf nodes in the given tree. For finding the leaf nodes, we will have to traverse the tree and check every node. 

While traversing the tree, whenever we hit a leaf node, we will store it in an array. To know if a node is a leaf or not, we will have to check if

  1. the left child is NULL and,
  2. the right child is NULL

If both the left and right child of a node is equal to NULL, it is a leaf node.

After the traversal of the tree is done, we will sort the array containing the leaf nodes in ascending order. After sorting the array, we will print the first K elements of the array as they are the K smallest elements of the given binary tree.

NOTE: If the input binary tree is a ‘perfect’ binary tree, we can easily find out the number of leaf nodes using the following two formulae,

  1. No. of leaf nodes = 2
  2. No. of leaf nodes = (n+1)/2 

Here ‘h’ refers to the height, and ‘n’ refers to the total number of nodes in the perfect binary tree. 

Steps of algorithm

  • Create an empty vector to store leaf nodes
  • Start preorder traversal of tree.

While root is not equal to NULL, recursively do the following steps

  • Check whether the node is a leaf node
    • Check if the left child is NULL
    • Check if the right child is NULL
  • Recur for left subtree
  • Recur for right subtree
  • Print first K elements of the vector

C++ Code

#include <bits/stdc++.h>
using namespace std;
//Structure of Node
struct Node
{
   int data;
   Node *left;
   Node *right;
   Node(int x)
   {
       data = x;
       left = right = NULL;
   }
};
void traverseAndStore(Node *root, vector<int> &v)
{
   if (root == NULL)
       return;
   // Checking whether left and right child of a node is NULL
   if (root->left == NULL && root->right == NULL)
   {
       // Pushing the data of leaf node in the vector
       v.push_back(root->data);
       return;
   }
   // Recur for left subtree
   traverseAndStore(root->left, v);
   // Recur for right subtree
   traverseAndStore(root->right, v);
}
int main()
{
   int K = 3;
   // Inserting the root of the tree
   Node *root = new Node(1);
   // Inserting the remaining nodes of the tree
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->left->right = new Node(5);
   root->right->left = new Node(6);
   root->right->right = new Node(7);
   root->left->left->left = new Node(8);
   // Vector to store the leaf nodes
   vector<int> leaf_nodes;
   // Function to traverse the tree in preorder fashion and store the leaf nodes
   traverseAndStore(root, leaf_nodes);
   // Sorting the leaf nodes vector in increasing order
   sort(leaf_nodes.begin(), leaf_nodes.end());
   // Printing the first k elements of the vector
   cout << "The K smallest leaf nodes are:" << endl;
   for (int i = 0; i < K; i++)
       cout << leaf_nodes[i] << " ";
   return 0;
}

 

Output:

The K smallest leaf nodes are:
5 6 7

Complexity Analysis

Time Complexity: O(N + L*logL)

O(N) time is taken to traverse the tree, and L*logL time is needed to sort the vector of leaf nodes, making the total time complexity O(N + L*logL).

Here N refers to the number of nodes, and L refers to the number of leaf nodes in the tree.

Space Complexity:  O(L + logN)

The O(L) term in the space complexity indicates we are using a vector of size L to store the leaf nodes. The O(logN) term in the space complexity refers to the fact that we are using recursion for the tree traversal. At any moment, the maximum elements in the recursion call stack will be O(logN) (logN is equal to the height of the tree).  So the total space complexity becomes O(L + logN).

Here N refers to the number of nodes in the tree, and L refers to the number of leaf nodes in the tree.

Frequently Asked Questions

What is a Binary Tree?

A binary tree, as the name suggests, a binary tree has a maximum of two children at every node of the tree. The two children are referred to as ‘left child’ and ‘right child’.

The nodes with no children are known as ‘leaf nodes’.

How to count the number of leaf nodes in a binary tree?

For counting the number of leaf nodes in a binary tree, we can traverse the tree recursively/iteratively and keep a count of the number of leaf nodes encountered. 

What is the preorder traversal of a tree?

Preorder traversal of a tree is a popular way to traverse any given tree. In preorder traversal, we visit the root first, then the left subtree, and finally the right subtree.

Preorder traversal is used to obtain the prefix expression from a given expression tree.

How to find the number of leaf nodes in a Perfect Binary Tree?

We can find the number of leaf nodes in a Perfect Binary even without traversing it if the height or number of nodes is known. The following two formulae can be used to find the number of leaf nodes,

  • No.of leaf nodes = 2
  • No. of leaf nodes = (n+1)/2

Here ‘h’ refers to the height, and ‘n’ refers to the total number of nodes in the perfect binary tree. 

You can read more about it here.

Conclusion

In this blog, we learned how to approach and solve this question “Find K smallest leaf nodes from a given Binary Tree.” We used preorder traversal to traverse the tree and stored the leaf nodes in a vector. Then we printed the first K elements of the sorted vector to obtain the output. 

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning, Ninja!

Previous article
Construct the Full K-ary Tree from its Preorder Traversal
Next article
Minimize the Sum of Node Values by filling a given empty Tree such that each node is GCD of its children
Live masterclass