Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Perfect Binary Tree?
3.
Examples of a Perfect Binary Tree
4.
Properties of a Perfect Binary Tree
5.
Check whether a Tree is a Perfect Binary Tree or Not
5.1.
Python
6.
Frequently Asked Questions
6.1.
Can a perfect binary tree have an odd number of levels?
6.2.
How does the structure of a perfect binary tree benefit algorithm performance?
6.3.
Is it possible to convert a regular binary tree into a perfect binary tree?
7.
Conclusion
Last Updated: May 25, 2024
Easy

Perfect Binary Tree

Author Riya Singh
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

A perfect binary tree is a special type of binary tree where every level is completely filled, except possibly the last level. In the last level, all nodes are as far left as possible. Perfect binary trees have a specific structure & properties that make them useful in various applications, such as efficient data storage & retrieval. 

Perfect Binary Tree

In this article, we will discuss the definition, examples, properties, & how to check if a given binary tree is perfect or not.

What is a Perfect Binary Tree?

A perfect binary tree is a type of binary tree where each node, except the leaf nodes, has exactly two child nodes & all the leaves are on the same level, or depth, in the tree. This means that every non-leaf node contributes to a fully filled level, making the tree symmetrical & balanced. The beauty of a perfect binary tree lies in its complete & orderly structure, which ensures that the tree remains as efficient as possible in terms of space & operations.

In simpler terms, if you picture a family tree where every parent has exactly two children, & every generation has the same number of family members, you're imagining a perfect binary tree. This structure allows for operations like search, insert, & delete to run in optimal time, which is crucial for performance in computing.

Here are some key points about perfect binary trees:

  1. All levels are completely filled, except possibly the last level.
     
  2. In the last level, all nodes are as far left as possible.
     
  3. The number of nodes in a perfect binary tree of height h is 2^(h+1) - 1.
     
  4. The number of leaf nodes in a perfect binary tree of height h is 2^h.
     
  5. The height of a perfect binary tree with n nodes is log(n+1) - 1.
     

Perfect binary trees are a subclass of complete binary trees, which means that every level, except possibly the last, is completely filled, & all nodes are as far left as possible.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Examples of a Perfect Binary Tree

Imagine a tree with just one node, the root; this is the simplest form of a perfect binary tree. Now, let’s add two children to this root, one on the left & one on the right; we now have a perfect binary tree with three nodes, with the structure appearing as a small "V" shape. This tree is perfect because each level is completely filled.

Now, let’s expand our tree. Give two children to each of the existing leaf nodes. Our tree now has seven nodes with three levels, & each level is fully populated with nodes. The tree maintains its perfect structure because every non-leaf node has two children & all leaf nodes are at the same depth.

Here is a visual representation of this tree:

Perfect Binary Tree

In this diagram:

  • 'A' is the root.
     
  • 'B' & 'C' are the children of 'A'.
     
  • 'D', 'E', 'F', & 'G' are the leaf nodes.

Properties of a Perfect Binary Tree

Perfect binary trees have several interesting properties that make them useful in various applications. Let's see some of these properties in detail : 

Number of nodes:

  1. The number of nodes in a perfect binary tree of height h is given by the formula:
  • Total number of nodes = 2^(h+1) - 1
     
  • Number of leaf nodes = 2^h
     
  • Number of internal nodes = 2^h - 1
     

For example, in a perfect binary tree of height 3, there are 2^(3+1) - 1 = 15 nodes in total, out of which 2^3 = 8 are leaf nodes & 2^3 - 1 = 7 are internal nodes.

  1. Height & number of nodes relationship:The height of a perfect binary tree with n nodes is given by:
  • Height = log(n+1) - 1
     

This means that the height of a perfect binary tree grows logarithmically with the number of nodes, making it a very efficient data structure for storing & retrieving data.

  1. Balance:Perfect binary trees are always balanced, meaning that the height difference between the left & right subtrees of any node is at most 1.
     
  2. Completeness:Perfect binary trees are also complete binary trees, which means that all levels, except possibly the last, are completely filled, & all nodes are as far left as possible.
     
  3. Symmetry:Perfect binary trees are symmetric, meaning that the left & right subtrees of any node are mirror images of each other.
     

These properties make perfect binary trees a valuable data structure in computer science, with applications in areas such as efficient searching, sorting, & indexing.

Check whether a Tree is a Perfect Binary Tree or Not

To determine if a binary tree is perfect, we can use specific criteria based on the properties we discussed earlier. A binary tree is perfect if all levels are completely filled. Here’s a straightforward method to check this using a programming example:

  1. Calculate Tree Depth: First, we need to find the depth of the tree. The depth is the number of edges in the longest path from the root to a leaf. This can be calculated using a simple recursive function.
     
  2. Check All Nodes: Once we have the depth, we traverse the tree to ensure every node either:
  • Has two children & isn’t a leaf, or
     
  • Is a leaf & is at the correct depth (the calculated tree depth).
     

Here is a Python function to determine if a binary tree is perfect:

  • Python

Python

class Node:

   def __init__(self, key):

       self.left = None

       self.right = None

       self.val = key

def calculate_depth(node):

   d = 0

   while node is not None:

       d += 1

       node = node.left

   return d

def is_perfect(root, depth, level=0):

   if root is None:

       return True

   if root.left is None and root.right is None:

       return depth == level + 1

   if root.left is None or root.right is None:

       return False

   return is_perfect(root.left, depth, level + 1) & is_perfect(root.right, depth, level + 1)

# Example usage

root = Node(10)

root.left = Node(20)

root.right = Node(30)

root.left.left = Node(40)

root.left.right = Node(50)

root.right.left = Node(60)

root.right.right = Node(70)




if is_perfect(root, calculate_depth(root)):

   print("The tree is perfect")

else:

   print("The tree is not perfect")

Output

The tree is perfect


This code first defines a binary tree node class, calculates the depth of the leftmost path (assuming the tree is perfect), & checks every node to ensure the tree meets the conditions of a perfect binary tree.

Frequently Asked Questions

Can a perfect binary tree have an odd number of levels?

Yes, a perfect binary tree can have an odd number of levels. The number of levels is determined by how many times you can repeatedly double the number of nodes starting from one, plus one level for the root.

How does the structure of a perfect binary tree benefit algorithm performance?

The structure of a perfect binary tree ensures that paths from the root to any leaf are the shortest possible. This uniformity allows operations like search, insert, and delete to be performed with maximum efficiency, typically in logarithmic time.

Is it possible to convert a regular binary tree into a perfect binary tree?

It is not possible to convert a regular binary tree into a perfect binary tree without restructuring the entire tree. A perfect binary tree requires a specific number of nodes that doubles at each level, which most binary trees do not naturally adhere to.

Conclusion

In this article, we have learned about perfect binary trees, including their definition, examples, and essential properties. Apart from this we also learned how to verify if a binary tree is perfect with proper example. Learning perfect binary trees is crucial for efficiently implementing and optimizing various algorithms and data structures, ensuring they operate with optimal performance. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.

Previous article
Complete Binary Tree
Next article
Threaded Binary Trees in Data Structure
Live masterclass