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.

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.

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.

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.

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.

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.

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.

Reference Interview Questions