Types of Trees: 1_Binary Tree

DEFINITION:

A tree is called a binary tree if each node has zero children, one child, or two children. The empty tree is also a valid binary tree. We can visualize a binary tree consisting of a root and two disjoint binary trees, called the left and right subtrees of the root.

PROPERTIES OF A BINARY TREES:

1. If h = height of a binary tree, then 

a. Maximum number of leaves = 2^h 

b. Maximum number of nodes = [2^(h + 1) - 1]

2.  If a binary tree contains m nodes at level l, it contains at most 2m nodes at level l + 1. 

3. Since a binary tree can contain at most one node at level 0 (the root), it can contain at most 2l node at level l. 

4. The total number of edges in a full binary tree with n node is n - 1.

TYPES OF BINARY TREES :

• Strict Binary Tree: A binary tree is called a strict binary tree if each node has exactly two children or no children.

• Full Binary Tree: A binary tree is called a full binary tree if each node has exactly two children and all leaf nodes are at the same level.

• Complete Binary Tree: Before defining the complete binary tree, let us assume that the height of the binary tree is h. In complete binary trees, if we give numbering for the nodes by starting at the root (let us say the root node has 1) then we get a complete sequence from 1 to the number of nodes in the tree. While traversing we should give numbering for NULL pointers also. A binary tree is called a complete binary tree if all leaf nodes are at height h or h – 1 and also without any missing number in the sequence.

CODE PROTOTYPE:

public class BNode

{

   private Object data;

   private BNode left, right;

   public BNode()

   {

      data=left=right=null;

   }

   public BNode(Object data)

   {

      this.data=data;

      left=right=null;

   }

}

BINARY TREE PARTS :

A Binary Tree node contains the following parts.

• Data
• Pointer to the left child
• Pointer to the right child

BASIC OPERATIONS OF BINARY TREES:

• Inserting an element into a tree
• Deleting an element from a tree
• Searching for an element
• Traversing the tree

AUXILIARY OPERATIONS OF BINARY TREES:

• Finding the size of the tree
• Finding the height of the tree
• Finding the level which has a maximum sum
• Finding the least common ancestor (LCA) for a given pair of nodes, and many more.

APPLICATIONS OF BINARY TREES:

Following are some of the applications where binary trees play an important role:

• Expression trees are used in compilers.
• Huffman coding trees that are used in data compression algorithms.
• Binary Search Tree (BST), which supports search, insertion, and deletion on a collection of items in O(logn) (average).
• Priority Queue (PQ), which supports search and deletion of minimum (or maximum) on a collection of items in logarithmic time (in the worst case).

ALGORITHMS

//TREE_SIZE

int TreeSize(struct node *root)

{

 if(root == 0) {

 return 0;

}

else

{

 return 1 + treeSize(root->left) + treeSize(root->right);

}

}

//TREE_HEIGHT 

int

treeHeight(struct node *root)

{

int lh; /* height of left subtree */

int rh; /* height of right subtree */

if(root == 0) {

return -1;

} else {

lh = treeHeight(root->left);

rh = treeHeight(root->right);

return 1 + (lh > rh ? lh : rh);

}

}

ANALYSIS:

Since both of these algorithms have the same structure, they both have the same asymptotic running time. We can compute this running time by observing that each recursive call to TreeSize or Tree height that does not get a null pointer passed to it gets a different node (so there are n such calls), and each call that does get a null pointer passed to it is called by a routine that doesn’t, and that there are at most two such calls per node. Since the body of each call itself costs O(1) (no loops), this gives a total cost of Θ(n). So these are all Θ(n) algorithms.

NOTE:

In the order defined above will produce the sequence {e, b,f,a,d,g} which we call flat(T). A binary search tree (BST) is a tree, where flat(T) is an ordered sequence. In other words, a binary search tree can be “searched” efficiently using this ordering property. A “balanced” binary search tree can be searched in O(log n) time, where n is the number of nodes in the tree.