Find K smallest leaf nodes in a given Binary Tree
Here given code implementation process.
/*
Java program
Find K smallest leaf nodes in a given Binary Tree
*/
import java.util.ArrayList;
import java.util.Collections;
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
System.out.print(" " + node.data);
inorder(node.right);
}
}
public void getLeafNodes(TreeNode node, ArrayList<Integer> result )
{
if (node != null)
{ if(node.left == null && node.right == null)
{
// Collecting a leaf node value
result.add(node.data);
}
// Recursively visit left and right subtree
getLeafNodes(node.left,result);
getLeafNodes(node.right,result);
}
}
public void smallestKLeaf(int k)
{
if(k < 0)
{
return;
}
if(this.root == null)
{
// When tree is empty
System.out.print("\n Empty Tree \n");
}
// This is used to collecting all leaf nodes
ArrayList<Integer> result = new ArrayList<Integer>();
// Display all tree nodes
System.out.print("\n All Tree Nodes \n");
this.inorder(this.root);
// Get leaf node
getLeafNodes(this.root , result);
System.out.print("\n ("+k+") Smallest leaf is ");
if(result.size() <= k)
{
// When all element is part of result
for (int i = 0; i < k && i < result.size() ; ++i )
{
System.out.print(" "+result.get(i));
}
}
else
{
// Need to sort element
Collections.sort(result);
for (int i = 0; i < k && i < result.size() ; ++i )
{
System.out.print(" "+result.get(i));
}
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.right.left = new TreeNode(15);
tree.smallestKLeaf(3);
}
}Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5// Include header file
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
C++ program
Find K smallest leaf nodes in a given Binary Tree
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
//Display Inorder view of binary tree
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
// Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
void getLeafNodes(TreeNode *node, vector <int> &result)
{
if (node != NULL)
{
if (node->left == NULL && node->right == NULL)
{
result.push_back(node->data);
}
// Recursively visit left and right subtree
this->getLeafNodes(node->left, result);
this->getLeafNodes(node->right, result);
}
}
void smallestKLeaf(int k)
{
if (k < 0)
{
return;
}
if (this->root == NULL)
{
// When tree is empty
cout << "\n Empty Tree \n";
}
// This is used to collecting all leaf nodes
vector < int > result;
// Display all tree nodes
cout << "\n All Tree Nodes \n";
this->inorder(this->root);
// Get leaf node
this->getLeafNodes(this->root, result);
cout << "\n (" << k << ") Smallest leaf is ";
if (result.size() <= k)
{
// When all element is part of result
for (int i = 0; i < k && i < result.size(); ++i)
{
cout << " " << result.at(i);
}
}
else
{
// Need to sort element
sort(result.begin(), result.end());
for (int i = 0; i < k && i < result.size(); ++i)
{
cout << " " << result.at(i);
}
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(11);
tree.root->right = new TreeNode(8);
tree.root->left->left = new TreeNode(3);
tree.root->left->right = new TreeNode(10);
tree.root->left->right->left = new TreeNode(7);
tree.root->right->left = new TreeNode(6);
tree.root->right->left->right = new TreeNode(9);
tree.root->right->right = new TreeNode(4);
tree.root->right->left->left = new TreeNode(5);
tree.root->right->right->right = new TreeNode(2);
tree.root->right->right->left = new TreeNode(15);
tree.smallestKLeaf(3);
return 0;
}Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5
/*
C# program
Find K smallest leaf nodes in a given Binary Tree
*/
// Include namespace system
using System;
using System.Collections.Generic;
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
Console.Write(" " + node.data);
inorder(node.right);
}
}
public void getLeafNodes(TreeNode node, List < int > result)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
result.Add(node.data);
}
// Recursively visit left and right subtree
getLeafNodes(node.left, result);
getLeafNodes(node.right, result);
}
}
public void smallestKLeaf(int k)
{
if (k < 0)
{
return;
}
if (this.root == null)
{
// When tree is empty
Console.Write("\n Empty Tree \n");
}
// This is used to collecting all leaf nodes
List < int > result = new List <int> ();
// Display all tree nodes
Console.Write("\n All Tree Nodes \n");
this.inorder(this.root);
// Get leaf node
getLeafNodes(this.root, result);
Console.Write("\n (" + k + ") Smallest leaf is ");
if (result.Count <= k)
{
// When all element is part of result
for (int i = 0; i < k && i < result.Count; ++i)
{
Console.Write(" " + result[i]);
}
}
else
{
// Need to sort element
result.Sort();
for (int i = 0; i < k && i < result.Count; ++i)
{
Console.Write(" " + result[i]);
}
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.right.left = new TreeNode(15);
tree.smallestKLeaf(3);
}
}Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5<?php
/*
Php program
Find K smallest leaf nodes in a given Binary Tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
function __construct()
{
$this->root = null;
}
//Display Inorder view of binary tree
public function inorder($node)
{
if ($node != null)
{
$this->inorder($node->left);
// Print node value
echo " ". $node->data;
$this->inorder($node->right);
}
}
public function getLeafNodes($node, &$result)
{
if ($node != null)
{
if ($node->left == null && $node->right == null)
{
// Collecting a leaf node value
$result[] = $node->data;
}
// Recursively visit left and right subtree
$this->getLeafNodes($node->left, $result);
$this->getLeafNodes($node->right, $result);
}
}
public function smallestKLeaf($k)
{
if ($k < 0)
{
return;
}
if ($this->root == null)
{
// When tree is empty
echo "\n Empty Tree \n";
}
// This is used to collecting all leaf nodes
$result = array();
// Display all tree nodes
echo "\n All Tree Nodes \n";
$this->inorder($this->root);
// Get leaf node
$this->getLeafNodes($this->root, $result);
echo "\n (". $k .") Smallest leaf is ";
if (count($result) <= $k)
{
// When all element is part of result
for ($i = 0; $i < $k && $i < count($result); ++$i)
{
echo " ". $result[$i];
}
}
else
{
// Need to sort element
sort($result);
for ($i = 0; $i < $k && $i < count($result); ++$i)
{
echo " ". $result[$i];
}
}
}
}
function main()
{
$tree = new BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(11);
$tree->root->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(3);
$tree->root->left->right = new TreeNode(10);
$tree->root->left->right->left = new TreeNode(7);
$tree->root->right->left = new TreeNode(6);
$tree->root->right->left->right = new TreeNode(9);
$tree->root->right->right = new TreeNode(4);
$tree->root->right->left->left = new TreeNode(5);
$tree->root->right->right->right = new TreeNode(2);
$tree->root->right->right->left = new TreeNode(15);
$tree->smallestKLeaf(3);
}
main();Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5// Node js
// Find K smallest leaf nodes in a given Binary Tree
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
//Display Inorder view of binary tree
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
getLeafNodes(node, result)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
result.push(node.data);
}
// Recursively visit left and right subtree
this.getLeafNodes(node.left, result);
this.getLeafNodes(node.right, result);
}
}
sortByValue (a, b)
{
return a < b;
}
smallestKLeaf(k)
{
if (k < 0)
{
return;
}
if (this.root == null)
{
// When tree is empty
process.stdout.write("\n Empty Tree \n");
}
// This is used to collecting all leaf nodes
var result = [];
// Display all tree nodes
process.stdout.write("\n All Tree Nodes \n");
this.inorder(this.root);
// Get leaf node
this.getLeafNodes(this.root, result);
process.stdout.write("\n (" + k + ") Smallest leaf is ");
if (result.Count <= k)
{
// When all element is part of result
for (var i = 0; i < k && i < result.Count; ++i)
{
process.stdout.write(" " + result[i]);
}
}
else
{
// Need to sort element
result.sort((a,b)=> a >= b);
for (var i = 0; i < k && i < result.length; ++i)
{
process.stdout.write(" " + result[i]);
}
}
}
}
function main()
{
var tree = new BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.right.left = new TreeNode(15);
tree.smallestKLeaf(3);
}
main();Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5# Python 3 program
# Find K smallest leaf nodes in a given Binary Tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
# Display Inorder view of binary tree
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.inorder(node.right)
def getLeafNodes(self, node, result) :
if (node != None) :
if (node.left == None and node.right == None) :
# get a leaf node
result.append(node.data)
# Recursively visit left and right subtree
self.getLeafNodes(node.left, result)
self.getLeafNodes(node.right, result)
def smallestKLeaf(self, k) :
if (k < 0) :
return
if (self.root == None) :
# When tree is empty
print("\n Empty Tree ")
# This is used to collecting all leaf nodes
result = []
# Display all tree nodes
print("\n All Tree Nodes ")
self.inorder(self.root)
# Get leaf node
self.getLeafNodes(self.root, result)
print("\n (", k ,") Smallest leaf is ", end = "")
if (len(result) <= k) :
# When all element is part of result
i = 0
while (i < k and i < len(result)) :
print(" ", result[i], end = "")
i += 1
else :
# Need to sort element
result.sort()
i = 0
while (i < k and i < len(result)) :
print(" ", result[i], end = "")
i += 1
def main() :
tree = BinaryTree()
#
# 1
# / \
# / \
# / \
# / \
# 11 8
# / \ / \
# 3 10 6 4
# / / \ / \
# 7 5 9 15 2
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(11)
tree.root.right = TreeNode(8)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(10)
tree.root.left.right.left = TreeNode(7)
tree.root.right.left = TreeNode(6)
tree.root.right.left.right = TreeNode(9)
tree.root.right.right = TreeNode(4)
tree.root.right.left.left = TreeNode(5)
tree.root.right.right.right = TreeNode(2)
tree.root.right.right.left = TreeNode(15)
tree.smallestKLeaf(3)
if __name__ == "__main__": main()Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
( 3 ) Smallest leaf is 2 3 5# Ruby program
# Find K smallest leaf nodes in a given Binary Tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Display Inorder view of binary tree
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
def getLeafNodes(node, result)
if (node != nil)
if (node.left == nil && node.right == nil)
result.push(node.data)
end
# Recursively visit left and right subtree
self.getLeafNodes(node.left, result)
self.getLeafNodes(node.right, result)
end
end
def smallestKLeaf(k)
if (k < 0)
return
end
if (self.root == nil)
# When tree is empty
print("\n Empty Tree \n")
end
# This is used to collecting all leaf nodes
result = []
# Display all tree nodes
print("\n All Tree Nodes \n")
self.inorder(self.root)
# Get leaf node
self.getLeafNodes(self.root, result)
print("\n (", k ,") Smallest leaf is ")
if (result.length <= k)
# When all element is part of result
i = 0
while (i < k && i < result.length)
print(" ", result[i])
i += 1
end
else
# Need to sort element
result = result.sort
i = 0
while (i < k && i < result.length)
print(" ", result[i])
i += 1
end
end
end
end
def main()
tree = BinaryTree.new()
#
# 1
# / \
# / \
# / \
# / \
# 11 8
# / \ / \
# 3 10 6 4
# / / \ / \
# 7 5 9 15 2
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(11)
tree.root.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(10)
tree.root.left.right.left = TreeNode.new(7)
tree.root.right.left = TreeNode.new(6)
tree.root.right.left.right = TreeNode.new(9)
tree.root.right.right = TreeNode.new(4)
tree.root.right.left.left = TreeNode.new(5)
tree.root.right.right.right = TreeNode.new(2)
tree.root.right.right.left = TreeNode.new(15)
tree.smallestKLeaf(3)
end
main()Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5/*
Kotlin program
Find K smallest leaf nodes in a given Binary Tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
//Display Inorder view of binary tree
fun inorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.inorder(node.left);
// Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
fun getLeafNodes(node: TreeNode ? , result: MutableList <Int> ): Unit
{
if (node != null)
{
if (node.left == null && node.right == null)
{
result.add(node.data);
}
// Recursively visit left and right subtree
this.getLeafNodes(node.left, result);
this.getLeafNodes(node.right, result);
}
}
fun smallestKLeaf(k: Int): Unit
{
if (k < 0)
{
return;
}
if (this.root == null)
{
// When tree is empty
print("\n Empty Tree \n");
}
// This is used to collecting all leaf nodes
var result: MutableList < Int > = mutableListOf < Int > ();
// Display all tree nodes
print("\n All Tree Nodes \n");
this.inorder(this.root);
// Get leaf node
this.getLeafNodes(this.root, result);
print("\n (" + k + ") Smallest leaf is ");
if (result.size <= k)
{
// When all element is part of result
var i: Int = 0;
while (i < k && i < result.size)
{
print(" " + result[i]);
i += 1;
}
}
else
{
// Need to sort element
result.sort();
var i: Int = 0;
while (i < k && i < result.size)
{
print(" " + result[i]);
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(11);
tree.root?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(10);
tree.root?.left?.right?.left = TreeNode(7);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.left?.right = TreeNode(9);
tree.root?.right?.right = TreeNode(4);
tree.root?.right?.left?.left = TreeNode(5);
tree.root?.right?.right?.right = TreeNode(2);
tree.root?.right?.right?.left = TreeNode(15);
tree.smallestKLeaf(3);
}Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5/*
Swift 4 program
Find K smallest leaf nodes in a given Binary Tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
//Display Inorder view of binary tree
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
func getLeafNodes(_ node: TreeNode? , _ result : inout [Int])
{
if (node != nil)
{
if (node!.left == nil && node!.right == nil)
{
result.append(node!.data);
}
// Recursively visit left and right subtree
self.getLeafNodes(node!.left, &result);
self.getLeafNodes(node!.right, &result);
}
}
func smallestKLeaf(_ k: Int)
{
if (k < 0)
{
return;
}
if (self.root == nil)
{
// When tree is empty
print("\n Empty Tree ");
}
// This is used to collecting all leaf nodes
var result = [Int]();
// Display all tree nodes
print("\n All Tree Nodes ");
self.inorder(self.root);
// Get leaf node
self.getLeafNodes(self.root, &result);
print("\n (", k ,") Smallest leaf is ", terminator: "");
if (result.count <= k)
{
// When all element is part of result
var i: Int = 0;
while (i < k && i < result.count)
{
print(" ", result[i], terminator: "");
i += 1;
}
}
else
{
// Need to sort element
result.sort();
var i: Int = 0;
while (i < k && i < result.count)
{
print(" ", result[i], terminator: "");
i += 1;
}
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(11);
tree.root!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(10);
tree.root!.left!.right!.left = TreeNode(7);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.left!.right = TreeNode(9);
tree.root!.right!.right = TreeNode(4);
tree.root!.right!.left!.left = TreeNode(5);
tree.root!.right!.right!.right = TreeNode(2);
tree.root!.right!.right!.left = TreeNode(15);
tree.smallestKLeaf(3);
}
main();Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
( 3 ) Smallest leaf is 2 3 5import scala.collection.mutable._ ;
/*
Scala program
Find K smallest leaf nodes in a given Binary Tree
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Display Inorder view of binary tree
def inorder(node: TreeNode): Unit = {
if (node != null)
{
this.inorder(node.left);
// Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
def getLeafNodes(node: TreeNode, result: ArrayBuffer[Int] ): Unit = {
if (node != null)
{
if (node.left == null && node.right == null)
{
result += node.data;
}
// Recursively visit left and right subtree
this.getLeafNodes(node.left, result);
this.getLeafNodes(node.right, result);
}
}
def smallestKLeaf(k: Int): Unit = {
if (k < 0)
{
return;
}
if (this.root == null)
{
// When tree is empty
print("\n Empty Tree \n");
}
// This is used to collecting all leaf nodes
var result = ArrayBuffer[Int]();
// Display all tree nodes
print("\n All Tree Nodes \n");
this.inorder(this.root);
// Get leaf node
this.getLeafNodes(this.root, result);
print("\n (" + k + ") Smallest leaf is ");
if (result.size <= k)
{
// When all element is part of result
var i: Int = 0;
while (i < k && i < result.size)
{
print(" " + result(i));
i += 1;
}
}
else
{
// Need to sort element
result = result.sorted;
var i = 0;
while (i < k && i < result.size)
{
print(" " + result(i));
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
/ \
/ \
/ \
11 8
/ \ / \
3 10 6 4
/ / \ / \
7 5 9 15 2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.right.left = new TreeNode(15);
tree.smallestKLeaf(3);
}
}Output
All Tree Nodes
3 11 7 10 1 5 6 9 8 15 4 2
(3) Smallest leaf is 2 3 5
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment