*Binary Tree Representations using Array:*

*In particular, we want to find out the maximum number of nodes in a binary tree of depth k, and the number of leaf nodes and the number of nodes of degree two in a binary tree. We present both these observations as lemma.*

*Lemma 5.1: [Maximum number of nodes]:**(1)The maximum number of nodes on level i of a binary tree is 2*

^{i}-1, i >= 1*(2)The maximum number of nodes in a binary tree of depth k is 2*

^{k}- 1, k >= 1

*Lemma 5.2: [Relation between number of leaf nodes and nodes of degree 2]:**Nonempty binary tree, T, if n*

_{0}is the number of leaf nodes and n_{2}the number of nodes of degree 2, then n_{0}= n_{2}+ 1.

*Binary Tree Representations using Array:**The numbering scheme used in it suggests out first representation of a binary tree in memory. Since the nodes are numbered from 1 to n, we can use a one-dimensional array to store the nodes. (We do not use the 0th position of the array.) Using Lemma 5.1 we can easily determine the locations of the parent, left child, and right child of any node, i, in the binary tree.*

**Lemma 5.3:***If a complete binary tree with n nodes (depth = └ log*

_{2}n +1┘) is represented sequentially, then for any node with index i, 1<= i <=n, we have:*(1) parent(i) is at └i/2┘ if i != 1 and if i = 1, i is at the root and has no parent.*

*(2) left_child(i) is at 2i if 2i <= n. If 2i > n, then i has no left child.*

*(3) right_child(i) is at (2i + 1), if (2i + 1) <= n. If (2i + 1) > n, then i has no right child.*

*Thanks*

*Mukesh Rajput*
## No comments:

## Post a Comment

Thanks

Mukesh Rajput