Binomial Trees

Binomial Trees are one of  the type of trees that are defined  recursively.A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1,n-2,n-3,n-4,……3,2,1,0.

Properties of Binomial Tree


Fig 1 : Binomial Tree

Binomial Tree of height/order(n)=0

When height =0 then single node will be present in Binomial tree(Fig 2).

Screen Shot 2014-05-30 at 3.53.29 PM

Fig 2 : Binomial Tree of Order 0



Binomial Tree at height (n)=1

When n=1 then 2=nodes will be present in the tree(Fig 3).

Screen Shot 2014-05-30 at 4.00.23 PM

Fig 3 : Binomial Tree of order 1



Binomial Tree of order=2

When n=2 then 2= 4 nodes will be present in the tree.The subtree is binomially  attached to the root node(Fig 4).

Screen Shot 2014-05-30 at 4.06.02 PM

Fig 4 : Binomial Tree of order 2



Binomial Tree of order 3

If order of tree is 3,then 23  nodes are present in the Binomial tree.The root is connected to subtrees of order 0(green color),1(red) and 2(black)  (Fig 5).

Screen Shot 2014-05-30 at 4.20.33 PM

Fig 5 : Binomial Tree of order 3



Bn  has  \tbinom n d nodes at depth d.

If we have a binomial tree of order n,then we can trace the number of nodes at any depth by  \tbinom n d.For e.g the no of nodes of binomial tree of order 4 at depth 2 will be 6.(Fig 6).In fig 7,number of nodes at level 2 is 6 and is shown by red highlighted area.

Screen Shot 2014-05-30 at 4.26.02 PM


Screen Shot 2014-05-30 at 4.33.36 PM

Fig 6 : Binomial Tree of order 4

Short URL:
Author: Cusp2207 on May 30, 2014
Category: Computer Science, Data Structures

Leave a Reply

Last articles