Find K smallest leaf nodes from a given Binary Tree

Debarati Ghatak
Last Updated: May 13, 2022

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.

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

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

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.

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

Q1 What is a Binary Tree?

Ans: 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’.

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

Ans: 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. 

Q3 What is the preorder traversal of a tree?

Ans: 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.

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

Ans: 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.

Key Takeaways

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. 

We hope you got to learn something valuable and useful from this blog.

Happy learning, Ninja!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think