Height of a complete binary tree (or Heap) with N nodes

Last Updated : 09 Aug, 2022

Consider a Binary Heap of size N. We need to find the height of it.

Examples:

Input : N = 6
Output : 2
        ()
      /    \
     ()     ()
    /  \    /
  ()    () ()

Input : N = 9
Output : 3
        ()
      /    \
     ()     ()
    /  \    /  \
  ()    () ()   ()
 / \
()  ()

Let the size of the heap be N and the height be h. If we take a few examples, we can notice that the value of h in a complete binary tree is floor(log₂N).

Examples:

 N    h
---------
 1    0
 2    1
 3    1
 4    2
 5    2
 .....
 .....

Implementation:

C++

// CPP program to find height of complete
// binary tree from total nodes.
#include <bits/stdc++.h>
using namespace std;
 
int height(int N)
{
    return floor(log2(N));
}
 
// driver node
int main()
{
    int N = 2;
    cout << height(N);
    return 0;
}

Java

// Java program to find height
// of complete binary tree
// from total nodes.
import java.lang.*;
 
class GFG {
     
    // Function to calculate height 
    static int height(int N)
    {
        return (int)Math.ceil(Math.log(N + 
                    1) / Math.log(2)) - 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 6;
        System.out.println(height(N));
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

Python 3

# Python 3 program to find 
# height of complete binary
# tree from total nodes.
import math
def height(N):
    return math.ceil(math.log2(N + 1)) - 1
 
# driver node
N = 6
print(height(N))
 
# This code is contributed by
# Smitha Dinesh Semwal

C#

// C# program to find height
// of complete binary tree
// from total nodes.
using System;
 
class GFG {
    static int height(int N)
    {
        return (int)Math.Ceiling(Math.Log(N 
                   + 1) / Math.Log(2)) - 1;
    }
 
    // Driver node
    public static void Main()
    {
        int N = 6;
        Console.Write(height(N));
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

PHP

<?php
// PHP program to find height
// of complete binary tree
// from total nodes.
 
function height($N)
{
    return ceil(log($N + 1, 2)) - 1;
}
 
// Driver Code
$N = 6;
echo height($N);
 
// This code is contributed by aj_36
?>

Javascript

<script>
 
    // Javascript program to find height
    // of complete binary tree
    // from total nodes.
     
    function height(N)
    {
        return Math.ceil(Math.log(N + 1) / Math.log(2)) - 1;
    }
     
      let N = 6;
      document.write(height(N));
         
</script>

Output

Time Complexity: O(1), Since performing constant operations.
Auxiliary Space: O(1), Since constant extra space is used.

Shashank_Pathak

Improve

K’th Smallest/Largest Element in Unsorted Array

Heap Sort for decreasing order using min heap

Some other type of Heap

Easy problems on Heap

Medium problems on Heap

Hard problems on Heap

Height of a complete binary tree (or Heap) with N nodes

C++

Java

Python 3

C#

PHP

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?