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

Types of Binary 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 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  Binary Tree zigzag level order Traversal

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

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

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