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 n where n is the order and degree of tree(Fig 1).
- Deleting roots yield binomial trees Bn-1,Bn-2,....0.
- Bn has 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 21 =2 nodes will be present in the tree(Fig 3).
Binomial Tree of order=2
When n=2 then 22 = 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.