Print all the leaf nodes of Binary Heap

0 0 5 minutes read

Given an array of N elements which denotes the array representation of binary heap, the task is to find the leaf nodes of this binary heap.

Examples:

Input: 
arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 4 5 6 7
Explanation:
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
Leaf nodes of the Binary Heap are:
4 5 6 7
         
Input: 
arr[] = {1, 2, 3, 4, 5,
         6, 7, 8, 9, 10}
Output: 6 7 8 9 10
Explanation:
                1
             /     \
            2       3
          /   \    / \
         4      5 6   7
       /   \   /
      8     9 10
Leaf Nodes of the Binary Heap are:
6 7 8 9 10

Approach: The key observation in the problem is that the every leaf node of the Binary Heap will be at the Height H or H -1, If H is the height of the Binary Heap. Therefore, the leaf nodes can be computed as follows:

Calculate the total height of the binary heap.
Traverse the array in reverse order and compare the height of each node to the compute height H of the Binary Heap.
If the height of the current node is H, then add the current node to the leaf nodes.
Otherwise, If the height of current node is H-1 and there are no child nodes, then also add the node as leaf node.

Below is the implementation of the above approach:

C++

// C++ implementation to print
// the leaf nodes of a Binary Heap
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the height of
// complete binary tree
int height(int N) { return (int)floor(log2(N + 1)); }
 
// Function to pr the leaf nodes
void prLeafNodes(vector<int> arrlist)
{
 
    for (int i = arrlist.size() - 1; i >= -0; i--)
        cout << arrlist[i] << " ";
}
 
// Function to find the leaf
// nodes of binary heap
void findLeafNodes(int arr[], int n)
{
 
    // Calculate the height of
    // the complete binary tree
    int h = height(n);
    vector<int> arrlist;
 
    for (int i = n - 1; i >= 0; i--) {
        if (height(i + 1) == h)
            arrlist.push_back(arr[i]);
        else if (height(i + 1) == h - 1
                 && n <= ((2 * i) + 1))
 
            // if the height if h-1,
            // then there should not
            // be any child nodes
            arrlist.push_back(arr[i]);
        else
            break;
    }
 
    prLeafNodes(arrlist);
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findLeafNodes(arr, n);
 
    return 0;
}
 
// This code is contributed by adityamaharshi21

Java

// Java implementation to print
// the leaf nodes of a Binary Heap
 
import java.lang.*;
import java.util.*;
class GFG {
 
    // Function to calculate height
    // of the Binary heap with given
    // the count of the nodes
    static int height(int N)
    {
        return (int)Math.ceil(
                   Math.log(N + 1)
                   / Math.log(2))
            - 1;
    }
 
    // Function to find the leaf
    // nodes of binary heap
    static void findLeafNodes(
        int arr[], int n)
    {
        // Calculate the height of
        // the complete binary tree
        int h = height(n);
 
        ArrayList<Integer> arrlist
            = new ArrayList<>();
 
        for (int i = n - 1; i >= 0; i--) {
            if (height(i + 1) == h) {
                arrlist.add(arr[i]);
            }
            else if (height(i + 1) == h - 1
                     && n <= ((2 * i) + 1)) {
 
                // if the height if h-1,
                // then there should not
                // be any child nodes
                arrlist.add(arr[i]);
            }
            else {
                break;
            }
        }
        printLeafNodes(arrlist);
    }
 
    // Function to print the leaf nodes
    static void printLeafNodes(
        ArrayList<Integer> arrlist)
    {
        for (int i = arrlist.size() - 1;
             i >= 0; i--) {
            System.out.print(
                arrlist.get(i) + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5,
                      6, 7, 8, 9, 10 };
        findLeafNodes(arr, arr.length);
    }
}

C#

// C# implementation to print
// the leaf nodes of a Binary Heap
using System;
using System.Collections.Generic;
class GFG{
 
// Function to calculate height
// of the Binary heap with given
// the count of the nodes
static int height(int N)
{
    return (int)Math.Ceiling(
                Math.Log(N + 1) /
                Math.Log(2)) - 1;
}
 
// Function to find the leaf
// nodes of binary heap
static void findLeafNodes(int []arr, 
                          int n)
{
    // Calculate the height of
    // the complete binary tree
    int h = height(n);
 
    List<int> arrlist = new List<int>();
 
    for (int i = n - 1; i >= 0; i--) 
    {
        if (height(i + 1) == h)
        {
            arrlist.Add(arr[i]);
        }
        else if (height(i + 1) == h - 1 && 
                 n <= ((2 * i) + 1)) 
        {
 
            // if the height if h-1,
            // then there should not
            // be any child nodes
            arrlist.Add(arr[i]);
        }
        else
        {
            break;
        }
    }
    printLeafNodes(arrlist);
}
 
// Function to print the leaf nodes
static void printLeafNodes(List<int> arrlist)
{
    for (int i = arrlist.Count - 1; i >= 0; i--) 
    {
        Console.Write(arrlist[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5,
                  6, 7, 8, 9, 10 };
    findLeafNodes(arr, arr.Length);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 implementation to print
# the leaf nodes of a Binary Heap
import math
 
def height(N):
 
    return math.log(N + 1) // math.log(2)
   
# Function to find the leaf
# nodes of binary heap
def findLeafNodes(arr, n):
 
    # Calculate the height of
    # the complete binary tree
    h = height(n)
     
    arrlist = []
   
    for i in range(n - 1,-1,-1):
        if (height(i + 1) == h):
            arrlist.append(arr[i])
        elif (height(i + 1) == h - 1 and n <= ((2 * i) + 1)):
   
            # if the height if h-1,
            # then there should not
            # be any child nodes
            arrlist.append(arr[i])
        else:
            break
 
    prLeafNodes(arrlist)
   
# Function to pr the leaf nodes
def prLeafNodes(arrlist):
 
    for i in range(len(arrlist) - 1,-1,-1):
        print(arrlist[i],end=" ")
   
# Driver Code
arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
findLeafNodes(arr, len(arr))
 
# This code is contributed by shinjanpatra

Javascript

<script>
// JavaScript implementation to print
// the leaf nodes of a Binary Heap
function height(N){
 
    return Math.floor(Math.log(N + 1) / Math.log(2))
}
   
// Function to find the leaf
// nodes of binary heap
function findLeafNodes(arr, n){
 
    // Calculate the height of
    // the complete binary tree
    let h = height(n)
     
    let arrlist = []
   
    for(let i = n - 1;i >= 0 ;i--){
        if (height(i + 1) == h)
            arrlist.push(arr[i])
        else if (height(i + 1) == h - 1 && n <= ((2 * i) + 1))
   
            // if the height if h-1,
            // then there should not
            // be any child nodes
            arrlist.push(arr[i])
        else
            break
    }
 
    prLeafNodes(arrlist)
}
   
// Function to pr the leaf nodes
function prLeafNodes(arrlist){
 
    for(let i = arrlist.length - 1 ; i>=-0; i--)
        document.write(arrlist[i]," ")
}
   
// Driver Code
 
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
findLeafNodes(arr, arr.length)
 
// This code is contributed by shinjanpatra
 
</script>

Output:

6 7 8 9 10

Performance Analysis:

Time Complexity: O(L), where L is the number of leaf nodes.
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!