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

Rate this post