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

Question

Suresh Chand · Accepted Answer

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: 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 2d nodes at level d.  Depth of d of a binary tree will have 2d+1-1 nodes (total nodes). Depth of d will have 2d leaves and 2d-1non-leaf nodes (internal nodes). No. of external nodes=No. of internal nodes+1. E.g. 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. Eg: 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.

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

Leave your Answer:

Hits Counter

Question

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

Leave your Answer: