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

  • There are 2n nodes in a binomial tree of order where n is the order and degree of tree(Fig 1).
  • Deleting roots yield binomial trees Bn-1,Bn-2,....0.
  • Bhas \tbinom n d nodes at depth d.
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).

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).

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).

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).

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.


Fig 6 : Binomial Tree of order 4
Rate this post


So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *