Binary Tree Data Structure

Binary Tree Data Structure

Binary tree data structure is define as  the node can have maximum two children. Each node can have either 0, 1 or 2 children.

 Each node of a binary tree has of three items:

• • data item
  • address of left child
  • address of right child

 

Properties of Binary Tree

1) The maximum number of nodes at each level ‘i’ of a this tree is 2^i.

2) The Maximum number of nodes in this tree of height ‘h’ is 2^h – 1.

3) In this tree, every node has 0 or 2 child.

If there are ‘n’ no. of nodes in the this tree.

 

The minimum height can be calculated as:

 

As we know that,

n = 2^h+1 -1

n+1 = 2^h+1

Taking log on both the sides,

log₂(n+1) = log2(2^h+1)

log₂(n+1) = h+1

h = log₂(n+1) – 1

 

The maximum height can be calculated as:

 

we know that,

n = h+1

h= n-1

 

Types of Binary Tree

1. Full Tree

2. Perfect Tree

3. Complete Tree

4. Degenerate or Pathological Tree

5. Skewed Tree

6. Balanced Tree

Binary Tree Implementation

struct node  
{  
   int data,  
   struct node *left, *right;  
}

Block of code of class containing left and right child of current node and key value

class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
class BinaryTree
{
    // Root of Binary Tree
    Node root;
 
    // Constructors
    BinaryTree(int key)
    {
        root = new Node(key);
    }
 
    BinaryTree()
    {
        root = null;
    }
 
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /*create root*/
        tree.root = new Node(1);
 
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
 
         
 
        tree.root.left.left = new Node(4);
            }
}