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
 the left child is NULL and,
 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,
 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.
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^{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:
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!