Page 106 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

Complete Binary Tree Notes

A complete binary tree of depth k is a tree with n nodes in which these n nodes can be numbered
sequentially from 1 to n, as if it would have been the fi rst n nodes in a full binary tree of depth k.
A complete binary tree with depth k = 3 is shown in Figure 5.5.
Figure 5.5: A Complete Binary Tree

A

B C

D E

5.2.2 Properties of a Binary Tree

Main properties of binary tree are:
1. If a binary tree contains n nodes, then it contains exactly n – 1 edges;
h
2. A Binary tree of height h has 2 – 1 nodes or less.
3. If we have a binary tree containing n nodes, then the height of the tree is at most n and at
least ceiling log (n + 1).
2
4. If a binary tree has n nodes at a level l then, it has at most 2n nodes at a level l + 1
0
5. The total number of nodes in a binary tree with depth k (root has depth zero) is N = 2 + 2
1
2
k
k+1
+ 2 + …….+ 2 = 2 – 1.
Task In figure 5.4 total no. of node present.

5.3 Binary Representation

If a binary tree is a complete binary tree, it can be represented using an array capable of holding
n elements where n is the number of nodes in a complete binary tree. If the tree is an array of n
elements, we can store the data values of the i node of a complete binary tree with n nodes at an
th
th
index i in an array tree. That means we can map node i to the i index in the array, and the parent
of node i will get mapped at an index i/2, whereas the left child of node i gets mapped at an index
2i and the right child gets mapped at an index 2i + 1.

Example: A complete binary tree with depth k = 3, having the number of nodes n = 5, can
be represented using an array of 5 as shown in fi gure.

LOVELY PROFESSIONAL UNIVERSITY 101