Binay Tree

Introduction:

• A binary tree is a tree in which no node can have more than two children.These children are described as left child and right child of the parent node.
• A binary tree T is defined as a finite set of nodes such that
  
  
  
  
  1. T is empty (ie) T has no nodes called the null tree or empty tree.
  2. There is a specially designated node called the root of the tree, and the remaining nodes are partitioned in to two disjointed sets T₁ and T₂,each of which is a binary tree.T₁ is called the left subtree and T₂ is called the right subtree.

• Example of a binary tree is shown in figure 1

• In the above binary tree A is the root node of the binar tree.B is the left child of A and C is the right child of A. So A is the parent node of B and C. B and C are the children of A.
• If a node has no child then its called a leaf node. In the above example nodes D,H,I,F,J are leaf nodes
• For a binary tree the maximum number of nodes at level i will be 2ⁱ considering root node is at level 0.
• If K is the depth of the tree then the maximum number of nodes that the tree can have is 2^K-1

Strictly binary tree:

• The tree is said to be strictly binary tree, if every non-leaf node in a binary tree has non-empty left and right sub trees
• (ie) every node in the strictly binary tree contains either no children or 2 children.
• figure 1 is not a strictly binary tree because node G has only one child
• A strictly binary tree with n leaves always contains 2n-1 nodes. The strictly binary tree in the below figure has 5 leaves such as D,E,F,H,I. here n=5.so the tree has 2*5-1 ie 9 nodes.The tree contains 9 nodes only.So in strictly binary tree given the number of leaves we can easily find the totla number of nodes in the tree.
• Strictly binary tree is also called 2-tree or extended binary tree.

• The main application of a 2-tree is to represent any algebraic expression such as [E=(a+b)/((c-d)*e)]using binary operation.