Binary Tree

 A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

A Binary Tree node contains following parts.

1. Data
2. Pointer to left child
3. Pointer to right child

class Node

{

    int key;

    Node left, right;

 

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}




public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

 

        /*create root*/

        tree.root = new Node(2);

 

        /* following is the tree after above statement

 

             2

            / \

         null null     */

        tree.root.left = new Node(7);

        tree.root.right = new Node(5);

                2

             /     \

           7        5

         /  \     /   \

       null null null null */

        tree.root.left.left = new Node(2);

        tree.root.left.right = new Node(6);

         

        /* 4 becomes left child of 2

                2

             /     \

           7        5

         /  \     /   \

        2 6 null null

      tree.root.left.right.left = new Node(5);

      tree.root.left.right.right = new Node(11);  

    }

}

Generally used ways for traversing trees

    Depth First Traversals: 
             (a) Inorder (Left, Root, Right) : 

                        4 2 5 1 3 
             (b) Preorder (Root, Left, Right) : 

                        1 2 4 5 3 
             (c) Postorder (Left, Right, Root) : 

                         4 5 2 3 1
 Breadth-First or Level Order Traversal:

    its traversing  like row by row.
            1 2 3 4 5