Data Structures and Algorithms - Old Questions

9. What are the types of binary tree? Compare between them.

A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.

• The first subset contains a single element called the root of the tree.
• The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.

Each element of a binary tree is called a node of the tree.

There are three types of binary tree:

1. Complete binary tree

A binary tree in which every internal nodes has exactly two children and all leaf nodes are at same level is called complete binary tree.

In complete binary tree:

• Tree of depth ‘d’ contains 2^d nodes at level d.
•  Depth of d of a binary tree will have 2^d+1-1 nodes (total nodes).
• Depth of d will have 2^d leaves and 2^d-1non-leaf nodes (internal nodes).
• No. of external nodes=No. of internal nodes+1.

E.g.

2. Strictly binary tree

A binary tree in which every node has either two or zero number of children is called strictly binary tree.

• In this tree every non-leaf node in a binary tree has nonempty left and right sub-trees.

• A strictly binary tree with n leaves always contains 2n-1 nodes.

E.g.

3. Almost complete binary tree

A almost complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position.

A binary tree is a almost complete binary tree (of height h , we take root node as 0 ) if and only if :-

• Level 0 to h-1 represent a full binary tree of height h-1
• One or more nodes in level h-1 may have  0, or 1 child nodes

• If F, G are nodes in level h-1, then F has  more child nodes than G if and only if F is to the left of G , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

E.g.