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
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput