Facebook

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

Fig 1 : A Binary Tree
Fig 1 : A Binary Tree

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.

Fig 2 : A Binary Tree
Fig 2 : A Binary Tree

 

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.
Fig 3 : Tree
  • 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.
Screen Shot 2014-05-01 at 3.08.58 PM
Fig 4 : Levels in binary tree

 

  • 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:

 

Screen Shot 2014-05-01 at 3.23.02 PM
Fig 5 : Degree of nodes

 

 

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

 

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar