Find K smallest leaf nodes from a given Binary Tree | C ++ program of the above approach ; Structure of binary tree node ; Function to create new node ; Utility function which calculates smallest three nodes of all leaf nodes ; Check if current root is a leaf node ; Traverse the left and right subtree ; Function to find the K smallest nodes of the Binary Tree ; Sorting the Leaf nodes array ; Loop to print the K smallest Leaf nodes of the array ; Driver Code ; Construct binary tree ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ( ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } void storeLeaf ( Node * root , vector < int > & arr ) { if ( ! root ) return ; if ( ! root -> left and ! root -> right ) { arr . push_back ( root -> data ) ; return ; } storeLeaf ( root -> left , arr ) ; storeLeaf ( root -> right , arr ) ; } void KSmallest ( Node * root , int k ) { vector < int > arr ; storeLeaf ( root , arr ) ; sort ( arr . begin ( ) , arr . end ( ) ) ; for ( int i = 0 ; i < k ; i ++ ) { if ( i < arr . size ( ) ) { cout << arr [ i ] << " ▁ " ; } else { break ; } } } int main ( ) { 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 ) ; KSmallest ( root , 3 ) ; return 0 ; }