Types of Binary Tree  

Difficulty Level Easy
Frequently asked in Delhivery Infosys MAQ
Theory Tree

Before we proceed, we first know what BT really is? Binary Tree is a type of data structure that is hierarchical in nature. A BT is represented by nodes where every node has left, a right pointer, and data as the weight of node. Each node can contain a maximum of 2 children which refer to the left and right child of a parent node.

Types of Binary TreePin

Why we need Binary Trees? | Why we use binary Trees?  

  • Using BT we can do fast search, insertion, and deletion on data(given in some priority order… like BST).
  • Using BT we can also find the closest item.
  • Store the data in a hierarchical manner(Ex. File system in the computer).
  • Implement BT using pointer which takes less time to perform any action.
  • Implement dictionaries with prefix lookup.
  • Fast search in the fixed text of the given dataset.

Properties of Binary Trees  

  1. Maximum number of nodes at any level: 2^L where L is a number of levels (0<=L<=H).
  2. Minimum and maximum number of nodes in a BT of height H: Minimum- H+1 and Maximum- 2^(H+1) – 1 where level 0 as height 0.
  3. Minimum possible height of a given BT having N nodes: log2(N+1)-1 where level 0 as height 0.
  4. Total number of leaf nodes: Total number of nodes with 2 children + 1.
  5. Minimum number of levels of a BT having L leaf nodes: (log2 L) +1.
See also
Relative Ranks Leetcode Solution

Types of Binary Trees  

Full Binary Trees

A Binary Tree whose root and intermediate nodes have 2 child nodes. In other words, we can also say that except leaf nodes every node has 2 child nodes.

Note: Number of leaf nodes in a full binary tree: Number of internal nodes+1.

Please click Like if you loved this article?

Full Binary TreesPin

Complete Binary Tree

A Binary Tree whose all levels except the last level are totally filled and all nodes are filled from left to right

Note: Binary Heap is an example of a complete binary tree.

Complete Binary TreePin

Perfect Binary Tree

A Binary Tree whose internal nodes and root node have 2 children and all leaf at the same level.

Note: Total number of nodes in Perfect Binary Tree: 2^H -1 where H is the height of BT.

Perfect Binary TreePin

Please click Like if you loved this article?

Balanced Binary Tree

A Binary Tree whose left subtree height h1 and right subtree height h2 then |h1-h2| <= 1.

Note: AVL and R-B tree maintain a balanced binary tree.

Balanced Binary TreePin

Pathological Binary Tree (Skewed BT/ Degenerate BT)

A Binary Tree whose all internal nodes have only one child may be left child or it may be a right child.

Note: Pathological BT Height: Number of nodes-1.

Pathological Binary TreePin

 

Please click Like if you loved this article?

Reference Interview Questions

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh