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 S1 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 2h -1 nodes . For e.g In Fig 4 height of tree is 4 and it can have 24 -1 =15 nodes at the max.
n = 2h -1
n + 1 =2h
log(n+1) = log(2h)
log2(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 log2(n+1).