Binary Tree Brush Up and Program

Binary Tree
Binary Tree is a tree if each node of it can have at most two branches .Each node o f binary tree may have zero ,one or two children.Empty tree is also a binary tree . The degree of a binary tree is 2.
















In the above figure you can see that every node has either 0,1 or 2 successors.

Complete Binary Tree  
It is binary tree in which every level except possibly the deepest , is filled i.e each node of tree can have at most two children  .













All the internal nodes have at most maximum 2 nodes . The external node may have 0,1 and 2 nodes.

Extended Binary Tree
A binary tree is said to be a  2 tree or extended binary tree if each node N has either 0 or 2 children . in such case node with 2 children are called internal nodes and nodes with 0 children are called external nodes.















Internal nodes are represented by circle and external nodes are represented by square.

Binary Search Tree

A binary search tree is a binary tree that is either empty or in which every node contains a key and satisfies the conditions:
(1)The key in the left child of a node (if it exists) is less than the key in its parent node.
(2)The key in the right child of a node (if it exists) is greater than the key in its parent node.

(3)The left and right subtrees of the root are again binary search trees.

Below is program to implement binary Search tree .

class BSTNode 
{
    int data;
    BSTNode right;
    BSTNode left;
    BSTNode(int d)
    {
        data=d;
    }
}
public class BinarySearchTree 
{
    public BSTNode insert(BSTNode p,int key)
    {
        if(p==null)
        {
        p=new BSTNode(key);
        }
        else if(key<p.data)     
        p.left=insert(p.left,key);
        else if(key>p.data)
        p.right=insert(p.right,key); 
        
        return p;
}
public void inorder(BSTNode p)
{
        if(p!=null)
        {
                inorder(p.left);
                System.out.print(p.data+" ");
                inorder(p.right);
        }
}
public void preorder(BSTNode p)
{
        if(p!=null)
        {
                System.out.print(p.data+" ");
                preorder(p.left);
                preorder(p.right);
        }
}
public void postorder(BSTNode p)
{
        if(p!=null)
        {
                
                postorder(p.left);
                postorder(p.right);
                System.out.print(p.data+" ");
        }
}
 
public static void main(String args[])
{
        BinarySearchTree BST =new BinarySearchTree();
        BSTNode root=null;
        root=BST.insert(root,4);
        root=BST.insert(root,2);
        root=BST.insert(root,1);
        root=BST.insert(root,3);
        root=BST.insert(root,5);
        System.out.print("\nInorder :-"+" ");
        BST.inorder(root);
        System.out.print("\nPreorder :-"+" ");
        BST.preorder(root);
        System.out.print("\nPostorder :-"+" ");
        BST.postorder(root);
}
}

Please comment if you find like the above post or find any mistake.