Find K Smallest Leaf Nodes from a given Binary Tree

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^h 
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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The K smallest leaf nodes are:
5 6 7

You can also try this code with Online C++ Compiler

Run Code

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^h 
• 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:

• Binary Tree vs Binary Search Tree
• Construct a Full K-Ary Tree From Preorder Traversal
• Smallest Subtree with All The Deepest Nodes
• Sum of Distance of All Nodes From a Given Node
• Find the Sum of Nodes on th Longest Path From Root To Leaf Nodes

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!