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 nodes at depth d.

Binomial Tree of height/order(n)=0

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

Binomial Tree at height (n)=1

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

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

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

Bn  has 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 .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. 