Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Types
3.
Full or Strict Binary Tree 
4.
Complete Binary Tree
5.
Perfect Binary Tree
6.
Degenerate Binary Tree
7.
Balanced Binary Tree
8.
Frequently Asked Questions
8.1.
What are the different types of traversals in Binary Trees?
8.2.
What are Binary Trees?
8.3.
What are some of the advantages of using binary trees?
8.4.
What is a Perfect Binary Tree?
8.5.
What is the need for balancing Binary Trees?
9.
Conclusion
Last Updated: Mar 27, 2024

Types of Binary trees

Author Malay Gain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction 

A binary tree consists of a finite number of nodes, either empty or having a root, and two disjoint binary trees called left and right subtrees. A binary tree node is made of a left pointer, a right pointer, and a data element.

There are mainly five types of Binary Trees frequently used. But sometimes, their names turn out confusing to identify distinctly. In this article, we will understand their unique properties and how they are different from each other through examples.

 

Types

Frequently used these types are -

  1. Full or Strict Binary Tree
  2. Complete Binary Tree
  3. Perfect Binary Tree
  4. Degenerate Binary Tree
  5. Balanced Binary Tree

 

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

Full or Strict Binary Tree 

Binary tree in which every node contains zero or two children nodes. In other words, the binary tree with all nodes having two children except leaf nodes.

Let’s visualize Full Binary Tree through examples

            10                            

           /    \                  

          5      3  

        /  \    /  \

       4   15  11   14

In the above binary tree, every node has two children nodes

Except for the leaf nodes at the last level.

 

             10

           /    \  

          5      3  

                /  \

               11   14

For this binary tree, 5,11,14 are leaf nodes that contain 0 children.

 

 

Complete Binary Tree

In this type of binary tree, all levels except the last level must be completely filled. In the last level, all nodes must be as left as possible.

 

Let’s visualize a Complete Binary Tree through examples

                            10                            

           /    \                  

          5      3  

        /  \    /  \

       4   15  11   14

In the above binary tree, all levels are completely filled.

 

             10                            

           /    \                  

          5      3  

        /  \    / 

       4   15  11 

Only the last level is not completely filled for this binary tree, and nodes 4, 5, and 11 are as much as to the left.

 

Perfect Binary Tree

A binary tree in which all internal nodes have two children and all leaf nodes are at the same level (i.e., last level).

 

Let’s visualize this type of Binary Tree through an example

                            10                            

           /    \                  

          5      3  

        /  \    /  \

       4   15  11   14

In the above binary tree, all internal nodes 10,5 and 3 have two children, and all leaf nodes are also at the same level.

 

So, all perfect binary trees are full as well as complete binary trees but not vice versa.

Also see, Perfect Binary Tree Specific Level Order Traversal

Degenerate Binary Tree

If each internal node has only one child node in a binary tree, it is called a Degenerate Binary tree.

Let’s visualize this type of binary tree through examples.

 

                          10                            

           /                     

          15     

         /   

        14

       /  

      12 

In the above binary tree, each internal node has only one child node(left child)

                           10                            

           /                     

          15     

           \   

           14

          /  

         12 

It is also Degenerate.

 

Balanced Binary Tree

If in a binary tree, the height of the left subtree and right subtree differ by at most 1, then it is a Balanced  Binary Tree.

AVL tree and Red-Black Tree come under the balanced binary tree.

 

Let’s visualize this type of binary tree through examples.

 

                            10                            

           /    \                  

          5      3  

        /  \      \

       4   15     14

In the above binary tree, the height difference of the left and right subtree is 0. So, it is balanced.

 

                            10                            

           /    \                  

          5      3  

                  \

                  14

                   \

                    11

 

For the above tree, the height difference of the left and right subtree is 2, i.e., greater than 1. So it is not balanced

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

What are the different types of traversals in Binary Trees?

Three are mainly three types of traversal techniques in Binary Trees.
In order
Preorder
Postorder

What are Binary Trees?

A tree is called a binary tree if every node has at most two children nodes.  A binary tree node constitutes a left pointer, a right pointer, and a data element. An empty binary tree (with zero nodes) is also a valid binary tree.

What are some of the advantages of using binary trees?

Insertion and deletion of data are faster than linked lists and arrays.
A hierarchical way of storing dataAccessing data is faster than a linked list also signifies the structural relationship existing in the given data.

What is a Perfect Binary Tree?

Binary tree in which all internal nodes have two children and all leaf nodes are at the same level (i.e., last level).

What is the need for balancing Binary Trees?

A balanced binary tree optimizes search time in the tree.
Search time complexity in a balanced binary tree is O(log n) in the worst case, but for an unbalanced tree, it is O(n), where n is the number of nodes. So maintaining a balanced tree is beneficial for large trees.

Conclusion

In this article, we have explored various types of binary trees and how they are different from each other.

Side by side, we should also learn about insertion, searching, and deletion operations in  Binary trees.

You can practice these concepts along with a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Recommended Problems:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning!

Previous article
Left View of a Binary Tree in Java
Next article
Binary Tree using dstructure library in Python
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass