(i)Complete binary tree - (ii) Degree of tree - (iii) Height of tree -

Marks: 3 M

Year: May 2014

Complete Binary tree

A complete binary tree at depth ‘d’ is the strictly binary tree, where all the leaves are at level d.

That is, if all the nodes at all levels except the last had two children, then there would be 1 = 20 node at level 1, 2 = 21 nodes at level 2, 4 = 22 nodes at level 3, and generally, 2i nodes at level i + 1. Such a tree is referred to as a complete binary tree.

Consider the following complete binary tree of depth 2 with root node A.

Figure 1: Complete Binary Tree

Degree of tree

The degree of a node is the number of partitions in the subtree which has that node as the root.

Nodes with degree 0 are called leaves.

The degree of a tree is the degree of the root node.

For example, the degree of a binary tree is 2, since a root node can have 2 children.

Height of tree

The height of a node is the length of the longest downward path between the node and a leaf node.

The height of a tree is the height of the root node.

For example, the height of the following tree is 4 (A-B-E-H-I).

Figure 2: Height of the tree is