Home » Technical Interview Questions » Tree Interview Questions » Types of Binary Tree

Types of Binary Tree


Reading Time - 2 mins

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 Tree

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.
READ  Construct Complete Binary Tree from its Linked List Representation

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.

Full Binary Trees

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 Tree

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 Tree

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 Tree

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 Tree

 

Reference Interview Questions

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions