Find all leaf nodes from preorder of a Binary Search Tree
Here given code implementation process.
/*
C Program
Find all leaf nodes from preorder of a Binary Search Tree
*/
#include <stdio.h>
#include <limits.h>
int findLeafNode(int preorder[], int n, int *index, int min, int max)
{
if ( *index < n)
{
if (preorder[ *index] >= min && preorder[ *index] <= max)
{
int node = preorder[ *index];
// Visit to next element
*index = *index + 1;
// check leaf in left and right subtree
int l = findLeafNode(preorder, n, index, min, node);
int r = findLeafNode(preorder, n, index, node, max);
if (l == -1 && r == -1)
{
// When node is leaf node
printf(" %d", node);
}
return 0;
}
}
return -1;
}
void *leafNode(int preorder[], int n)
{
if (n > 0)
{
int index = 0;
findLeafNode(preorder, n, &index, INT_MIN, INT_MAX);
}
}
int main()
{
int preorder[] = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = sizeof(preorder) / sizeof(preorder[0]);
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
leafNode(preorder, n);
return 0;
}Output
11 14 18 22// Java Program for
// Find all leaf nodes from preorder of a Binary Search Tree
public class DetectLeafNode
{
public int index;
public DetectLeafNode()
{
this.index = 0;
}
public boolean findLeafNode(int[] preorder,
int n, int min, int max)
{
if (this.index < n)
{
if (preorder[index] >= min && preorder[this.index] <= max)
{
int node = preorder[this.index];
// Visit to next element
this.index = this.index + 1;
// check leaf in left and right subtree
boolean l = findLeafNode(preorder, n, min, node);
boolean r = findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
System.out.print(" " + node);
}
return false;
}
}
return true;
}
public void leafNode(int[] preorder, int n)
{
if (n > 0)
{
this.index = 0;
findLeafNode(preorder, n,
Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
}
public static void main(String[] args)
{
DetectLeafNode task = new DetectLeafNode();
int[] preorder = {
15 , 13 , 12 , 11 , 14 , 20 ,
19 , 17 , 18 , 21 , 22
};
int n = preorder.length;
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}
}Output
11 14 18 22// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
// C++ Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
{
public: int index;
DetectLeafNode()
{
this->index = 0;
}
bool findLeafNode(int preorder[],
int n, int min, int max)
{
if (this->index < n)
{
if (preorder[this->index] >= min &&
preorder[this->index] <= max)
{
int node = preorder[this->index];
// Visit to next element
this->index = this->index + 1;
// check leaf in left and right subtree
bool l = this->findLeafNode(preorder, n, min, node);
bool r = this->findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
cout << " " << node;
}
return false;
}
}
return true;
}
void leafNode(int preorder[], int n)
{
if (n > 0)
{
this->index = 0;
this->findLeafNode(preorder, n, INT_MIN, INT_MAX);
}
}
};
int main()
{
DetectLeafNode *task = new DetectLeafNode();
int preorder[] = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = sizeof(preorder) / sizeof(preorder[0]);
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task->leafNode(preorder, n);
return 0;
}Output
11 14 18 22package main
import "math"
import "fmt"
// Go Program for
// Find all leaf nodes from preorder of a Binary Search Tree
type DetectLeafNode struct {
index int
}
func getDetectLeafNode() * DetectLeafNode {
var me *DetectLeafNode = &DetectLeafNode {}
me.index = 0
return me
}
func(this *DetectLeafNode) findLeafNode(preorder[] int,
n int, min int, max int) bool {
if this.index < n {
if preorder[this.index] >= min && preorder[this.index] <= max {
var node int = preorder[this.index]
// Visit to next element
this.index = this.index + 1
// check leaf in left and right subtree
var l bool = this.findLeafNode(preorder, n, min, node)
var r bool = this.findLeafNode(preorder, n, node, max)
if l && r {
// When node is leaf node
fmt.Print(" ", node)
}
return false
}
}
return true
}
func(this DetectLeafNode) leafNode(preorder[] int, n int) {
if n > 0 {
this.index = 0
this.findLeafNode(preorder, n, math.MinInt64, math.MaxInt64)
}
}
func main() {
var task * DetectLeafNode = getDetectLeafNode()
var preorder = [] int {
15,
13,
12,
11,
14,
20,
19,
17,
18,
21,
22,
}
var n int = len(preorder)
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n)
}Output
11 14 18 22// Include namespace system
using System;
// Csharp Program for
// Find all leaf nodes from preorder of a Binary Search Tree
public class DetectLeafNode
{
public int index;
public DetectLeafNode()
{
this.index = 0;
}
public Boolean findLeafNode(int[] preorder,
int n, int min, int max)
{
if (this.index < n)
{
if (preorder[this.index] >= min &&
preorder[this.index] <= max)
{
int node = preorder[this.index];
// Visit to next element
this.index = this.index + 1;
// check leaf in left and right subtree
Boolean l = this.findLeafNode(preorder, n,
min, node);
Boolean r = this.findLeafNode(preorder, n,
node, max);
if (l && r)
{
// When node is leaf node
Console.Write(" " + node);
}
return false;
}
}
return true;
}
public void leafNode(int[] preorder, int n)
{
if (n > 0)
{
this.index = 0;
this.findLeafNode(preorder, n,
int.MinValue, int.MaxValue);
}
}
public static void Main(String[] args)
{
DetectLeafNode task = new DetectLeafNode();
int[] preorder = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = preorder.Length;
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}
}Output
11 14 18 22<?php
// Php Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
{
public $index;
public function __construct()
{
$this->index = 0;
}
public function findLeafNode($preorder, $n, $min, $max)
{
if ($this->index < $n)
{
if ($preorder[$this->index] >= $min &&
$preorder[$this->index] <= $max)
{
$node = $preorder[$this->index];
// Visit to next element
$this->index = $this->index + 1;
// check leaf in left and right subtree
$l = $this->findLeafNode($preorder, $n, $min, $node);
$r = $this->findLeafNode($preorder, $n, $node, $max);
if ($l && $r)
{
// When node is leaf node
echo(" ".$node);
}
return false;
}
}
return true;
}
public function leafNode($preorder, $n)
{
if ($n > 0)
{
$this->index = 0;
$this->findLeafNode($preorder, $n, -PHP_INT_MAX, PHP_INT_MAX);
}
}
}
function main()
{
$task = new DetectLeafNode();
$preorder = array(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
$n = count($preorder);
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
$task->leafNode($preorder, $n);
}
main();Output
11 14 18 22// Node JS Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
{
constructor()
{
this.index = 0;
}
findLeafNode(preorder, n, min, max)
{
if (this.index < n)
{
if (preorder[this.index] >= min &&
preorder[this.index] <= max)
{
var node = preorder[this.index];
// Visit to next element
this.index = this.index + 1;
// check leaf in left and right subtree
var l = this.findLeafNode(preorder, n, min, node);
var r = this.findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
process.stdout.write(" " + node);
}
return false;
}
}
return true;
}
leafNode(preorder, n)
{
if (n > 0)
{
this.index = 0;
this.findLeafNode(preorder, n,
-Number.MAX_VALUE, Number.MAX_VALUE);
}
}
}
function main()
{
var task = new DetectLeafNode();
var preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
var n = preorder.length;
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}
main();Output
11 14 18 22import sys
# Python 3 Program for
# Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode :
def __init__(self) :
self.index = 0
def findLeafNode(self, preorder, n, min, max) :
if (self.index < n) :
if (preorder[self.index] >= min and preorder[self.index] <= max) :
node = preorder[self.index]
# Visit to next element
self.index = self.index + 1
# check leaf in left and right subtree
l = self.findLeafNode(preorder, n, min, node)
r = self.findLeafNode(preorder, n, node, max)
if (l and r) :
# When node is leaf node
print(" ", node, end = "")
return False
return True
def leafNode(self, preorder, n) :
if (n > 0) :
self.index = 0
self.findLeafNode(preorder, n, -sys.maxsize, sys.maxsize)
def main() :
task = DetectLeafNode()
preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
n = len(preorder)
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 19 21
# / / \
# 11 17 22
# \
# 18
# -----------------------
# Binary search tree
task.leafNode(preorder, n)
if __name__ == "__main__": main()Output
11 14 18 22# Ruby Program for
# Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
# Define the accessor and reader of class DetectLeafNode
attr_reader :index
attr_accessor :index
def initialize()
self.index = 0
end
def findLeafNode(preorder, n, min, max)
if (self.index < n)
if (preorder[self.index] >= min && preorder[self.index] <= max)
node = preorder[self.index]
# Visit to next element
self.index = self.index + 1
# check leaf in left and right subtree
l = self.findLeafNode(preorder, n, min, node)
r = self.findLeafNode(preorder, n, node, max)
if (l && r)
# When node is leaf node
print(" ", node)
end
return false
end
end
return true
end
def leafNode(preorder, n)
if (n > 0)
self.index = 0
self.findLeafNode(preorder, n,
-(2 ** (0. size * 8 - 2)),
(2 ** (0. size * 8 - 2)))
end
end
end
def main()
task = DetectLeafNode.new()
preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
n = preorder.length
# 15
# / \
# / \
# / \
# 13 20
# / \ / \
# 12 14 19 21
# / / \
# 11 17 22
# \
# 18
# -----------------------
# Binary search tree
task.leafNode(preorder, n)
end
main()Output
11 14 18 22// Scala Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode(var index: Int)
{
def this()
{
this(0) ;
}
def findLeafNode(preorder: Array[Int], n: Int,
min: Int, max: Int): Boolean = {
if (this.index < n)
{
if (preorder(index) >= min && preorder(this.index) <= max)
{
var node: Int = preorder(this.index);
// Visit to next element
this.index = this.index + 1;
// check leaf in left and right subtree
var l: Boolean = findLeafNode(preorder, n, min, node);
var r: Boolean = findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
print(" " + node);
}
return false;
}
}
return true;
}
def leafNode(preorder: Array[Int], n: Int): Unit = {
if (n > 0)
{
this.index = 0;
findLeafNode(preorder, n, Int.MinValue, Int.MaxValue);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: DetectLeafNode = new DetectLeafNode();
var preorder: Array[Int] = Array(
15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
var n: Int = preorder.length;
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}
}Output
11 14 18 22import Foundation;
// Swift 4 Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
{
var index: Int;
init()
{
self.index = 0;
}
func findLeafNode(_ preorder: [Int],
_ n: Int, _ min: Int, _ max: Int) -> Bool
{
if (self.index < n)
{
if (preorder[self.index] >= min &&
preorder[self.index] <= max)
{
let node: Int = preorder[self.index];
// Visit to next element
self.index = self.index + 1;
// check leaf in left and right subtree
let l: Bool = self.findLeafNode(preorder, n, min, node);
let r: Bool = self.findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
print(" ", node, terminator: "");
}
return false;
}
}
return true;
}
func leafNode(_ preorder: [Int], _ n: Int)
{
if (n > 0)
{
self.index = 0;
let _ = self.findLeafNode(preorder, n, Int.min, Int.max);
}
}
}
func main()
{
let task: DetectLeafNode = DetectLeafNode();
let preorder: [Int] = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
let n: Int = preorder.count;
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}
main();Output
11 14 18 22// Kotlin Program for
// Find all leaf nodes from preorder of a Binary Search Tree
class DetectLeafNode
{
var index: Int;
constructor()
{
this.index = 0;
}
fun findLeafNode(preorder: Array < Int > ,
n: Int, min: Int, max: Int): Boolean
{
if (this.index < n)
{
if (preorder[this.index] >= min &&
preorder[this.index] <= max)
{
val node: Int = preorder[this.index];
// Visit to next element
this.index = this.index + 1;
// check leaf in left and right subtree
val l: Boolean = this.findLeafNode(preorder, n, min, node);
val r: Boolean = this.findLeafNode(preorder, n, node, max);
if (l && r)
{
// When node is leaf node
print(" " + node);
}
return false;
}
}
return true;
}
fun leafNode(preorder: Array < Int > , n: Int): Unit
{
if (n > 0)
{
this.index = 0;
this.findLeafNode(preorder, n,
Int.MIN_VALUE, Int.MAX_VALUE);
}
}
}
fun main(args: Array < String > ): Unit
{
val task: DetectLeafNode = DetectLeafNode();
val preorder: Array < Int > = arrayOf(
15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
val n: Int = preorder.count();
/*
15
/ \
/ \
/ \
13 20
/ \ / \
12 14 19 21
/ / \
11 17 22
\
18
-----------------------
Binary search tree
*/
task.leafNode(preorder, n);
}Output
11 14 18 22
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