Thursday, 23 November 2017

Properties of Binary Trees: A Non-Linear Data Structure

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 2i -1, i >= 1
(2)The maximum number of nodes in a binary tree of depth k is 2k - 1, k >= 1

Lemma 5.2 [Relation between number of leaf nodes and nodes of degree 2]:

Nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes of degree 2, then n0 = n2 + 1.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput