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.

- There are
**2**^{n }nodes in a binomial tree of order**n**where n is the order and degree of tree(Fig 1). - Deleting roots yield binomial trees
**B**_{n-1},B_{n-2},….0. - B
_{n }has**nodes**at depth d.

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

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

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

If order of tree is 3,then 2^{3 }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)**.**

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.

In order to **delete** elements from **B-Tree** we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.

**Example**

Consider a B-tree of Fig 1.Say we want to delete **2,21,10,3 and 4** step by step from the tree.

**Delete 2**

- 2 is present in
**node b**.Deletion of 2 do not violate any property of B-tree,so we delete**2 directly**from node**b**.(Fig 2)

**Delete 21**

- Deletion of 21 cannot be done directly.It causes node e to
**underflow**so elements are**redistributed**among**c,g and e**(Fig 3).**10**remains in**c**.**12**is stored in**g**and**13**is stored in**e**.

**Delete 10**

- Deletion of 10 again cannot be done directly.It causes
**node c**to**underflow**which further causes parent node**g**to combine with**f and a**and tree shrinks by one level.**3,7 and 9**are stored in**a**,**1 in b**,**4 and 5**in**d,8**in**h****,12 and 13**in**e**(Fig 4).

**Delete 3**

- Deletion of
**3**causes**4**to move in**a**(Fig 5).

**Delete 4**

- Deletion of
**4**needs redistribution of the keys in the**subtrees of 4**; however, nodes**b and d**do not have**enough**keys to redistribute without causing an underflow. Thus, nodes**b and d**are combined together(Fig 6).

The B-tree is a generalization of a** binary search tree ** in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

- The
**data items**are stored at**leaves**. - Every
**node**has between**M/2**and**M**children where**M**is a positive integer greater than**1**. **M**is the**order**as well as**height**of tree.- The non leaf nodes store up to
**M-1**keys. - The root is either a leaf or has between two and M children.
- All leaves are at the
**same depth**and have between**[L/2]**and**L**children.

The insertion in b-tree is done such that they satisfy all the properties listed above.

**Example**

Consider a B-Tree of** order 4** and we need to insert **5,3,21,9,1,13,2,7,10,12,4,8**.Each node can have **at most 4 pointers** and **3 keys (M-1) **or ** at least 2 pointers** and **1 key**.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

- Create a node
**a**and insert**5**.(Fig 1) - Insert
**3**to the left of**5 (3<5)**. - Insert
**21**to the right of**5(21 >5).** - In order to insert 9 split node
**a**into**b and c**as 9 cannot be accommodated in node a(**Max keys =3**).The**left pointer**of**9**points to**3**and**5****((3 ,5) <9)**and the**right pointer points**to**21(21 >9**),

- Insert
**1**in node**b (1<3)**(Fig 2). - Insert
**13**in node**c(13>9 and 13 <21).** **2**cannot be directly inserted in node**b**- In order to insert 2 split
**b**into**b and d**. **3**gets**stored**in node**a**.- Store
**1 and 2**in node**b**. - Store
**5**in node**d**.

- In order to insert 2 split

- Insert
**7**in node**d**Â .**(7 >5 and 7<9)**(Fig 3) - Insert
**10**in node**c**(**10 >9 and 10 <13**). - Now
**12**cannot be directly inserted in node**c**.- Split
**c**into**c and e**. **12**is then inserted in node Â**c**.**21**is stored in**e**.

- Split

- Insert
**4**in node**d**(**4 >3 and 4 <5**).(Fig 4) **8**cannot be inserted in**d**directly.- Split
**d**into**f and g** - Split
**f**into**f and h**. **8**is inserted in**h**.

- Split

Traversal means to **move across/visit **each and every **node** in the tree.There are three techniques to traverse a Binary Tree :

- Preorder
- Inorder
- Postorder

In preorder traversal,firstly the **root** is traversed then **left subtree** and in the last** right subtree**(Fig 1)**.**

Consider the following binary tree(Fig 2) :

**Root** is traversed in the **beginning** so **10** is** visited** at the **firs**t.After this **left sub-tree** is traversed. (Fig 3). In the** left subtree** **22** is the root of **44** and **25**,so** 22** is visited after 10 followed by left child i.e.**44**.**25** is the **right child** and is the root node of **17** and **88**.**44** is followed by **25** then **17** and **88**.After visiting left sub-tree traversal of right subtree is done.**13** is visited and followed by left child i.e.**46**.

In In-order traversal,**left subtree** is traversed in the **beginning ** followed by **root ** which is further followed by **right sub-tree**(Fig 4).

Consider the following binary tree(Fig 5) :

In post-order traversal left subtree is traversed first followed by right subtree and further followed by root.

Consider the following binary tree(Fig 5) :

**Binary trees** in memory can be represented by

- Array
- Linked Lists

Binary Trees can be represented using **1-D array** in memory(Fig 1).The rule to store** binary tree** in array are :

- The values of binary tree is stored in an array called as
**tree**. - The root of the tree is stored at
**first location**i.e. at**tree[0](0 index)**. - The
**left child**of tree is stored at**2i +1**and right child is stored at^{ }**2i+2**location. -
The
**maximum size**of the array tree is given as**2**, where^{d+1}-1**d**is the**depth**of the**tree**. -
An
**empty tree**or**sub-tree**is specified using**NULL**. If**tree[0] = NULL**, then it means that**tree is empty.**

In linked list representation,every** node** of the tree has **three parts** : the **data**/root element,the** pointer** to the** left node** and the **pointer** to the **right node**(Fig 2).In C,tree is built using structures by the following way :

struct node { struct node* left; int data; struct node* right; };

**Binary Trees** are the** data structure** defined by collection of elements called **nodes**.They are one of the efficient data structures for searching and insertion operations.The **topmost** node of binary tree is known as** ROOT** node pointed by ROOT pointer.Root node has ** left child/successor** and **right child/successor** pointed by left and right pointers(Fig 1).

The left child further may or may not have successors and the right child may/may not have further successors.If nodes are split into further nodes then a tree is formed known as **subtree** of root.The left node of root(divided into further nodes) are collectively called as **left subtree** and right node(divided into further nodes) are called as **right subtree**(Fig 2).Every node in a binary tree has **0,1 or at most 2 successors**.The node which **does not have** any successor is called as **leaf node** or **terminal node**.

**Sibling**- If**T**is a**tree**and**N**is any**node**that has**left**child/**successor S1**and**right successor S2**,then**N**is the**parent**of**S**1 and**S2**.**S1**and**S2**are called as**siblings**(Fig 3).Every node other than the root node has a parent.Thus all**nodes**which are at**same level**and have**same parent**are known as**siblings**.In Fig 3,**2 and 3**are**siblings**and**1**is the**parent**of**2 and 3.**

**Level Number**: It is the**level**of the**node**.The**root node**is at**level 0**and its**successors**are at**one level higher**than previous i.e at**level****1**.The further successors of left and right child are at again one level higher i.e.at 2.Thus level number of all child nodes are**+1 level**of their**parent**level.

**Degree**– It is equal to**number of children**that a**node**has.It can be**0,1 or 2**in case of binary tree.The degree of**leaf nodes**is**0**.The degree of nodes in Fig 4 is as given below:

**In-Degree**– It is the number of**edges arriving**at that**node**.The in-degree of**root node**is**0**as no edge arrives at root node.**Out-degree**– It is the number of**edges**that**exits**from that**node**.**Leaf node**– It is the**terminal node**having**no children**.**Directed edge**-**Line**drawn from**node**to any of the**successor**is known as directed edge.A binary tree of**N**nodes has exactly**N-1**edges.**Path**– A sequence of**consecutive edges**is known as Path.**Ancestor nodes**– All the**nodes**along the**path**from the**root node**to that**node**.**Descendant nodes**– All the nodes along the path from that**node**to**leaf node**.**Depth**– It is the**length**of path from**root node**to node**N**.A binary tree of height has at least h nodes and at most 2^{h }-1 nodes . For e.g In Fig 4 height of tree is 4 and it can have 2^{4 }-1 =15 nodes at the max.

n = 2^{h} -1

n + 1 =2^{h}

log(n+1) = log(2^{h)}

** log _{2}(n+1) = h**

** n** is the** number** of nodes and **h** is the **height** of tree. The **height** of binary tree is at least** n** and at most **log _{2}(n+1)**.