# Binary Trees

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

### Terms associated with Binary Tree

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

## Comments

So empty here ... leave a comment!