Skip to main content

Find all leaf nodes from preorder of a Binary Search Tree

Find all leaf nodes from preorder of BST

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 22
package 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 22
import 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 22
import 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
Last updated on by Kalkicode




Comment

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