Binary Tree in Java

Binary Tree or Binary Search Tree
Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical 
data structures. Elements with no children are called leaves.

package datastructure.tree;
public class BinaryTreeTest {
    static class Node {
        Node left;
        Node right;
        int data;
        public Node(int d) {
            this.data = d;
        }
    }

    static Node root = null;
    public static void main(String[] args) {
        root = new Node(50); //Making 5 as Root node    

        BinaryTreeTest object = new BinaryTreeTest();
        object.startFunctions();
        System.out.println("Total Node Count: "+object.countNodes(root));
        System.out.println("Search Node 60: "+object.search(root, 60));
    }

    public void startFunctions() {        
        System.out.println("Building tree with root value " + root.data);
        insert(root, 30);
        insert(root, 20);
        insert(root, 40);
        insert(root, 70);
        insert(root, 60);
        insert(root, 80);
        System.out.println("Traversing Tree InOrder");
        printInOrder(root);        
        System.out.println("Traversing Tree PreOrder");
        printPreOrder(root);        
        System.out.println("Traversing Tree PostOrder");
        printPostOrder(root);
    }

    public void insert(Node node, int value) {
        if(value<node.data) { //To go to left side
            if(node.left == null) {
                node.left = new Node(value);
                System.out.println("  Inserted " + value + " to left of " + node.data);
            }
            else {
                insert(node.left, value);
            }
        } 
        else if(value>node.data) { //To go to right side
            if(node.right == null) {
                node.right = new Node(value);
                System.out.println("  Inserted " + value + " to right of "+ node.data);
            } else {
                insert(node.right, value);
            }
        }
    }
    public void printInOrder(Node node) {
        if(node != null) {
            printInOrder(node.left);
            System.out.println("  InOrder Traversed " + node.data);
            printInOrder(node.right);
        }
    }
    public void printPreOrder(Node node) {
        if(node != null) {
            System.out.println("  PreOrder Traversed " + node.data);
            printPreOrder(node.left);
            printPreOrder(node.right);
        }
    }
    public void printPostOrder(Node node) {
        if(node != null) {
            printPostOrder(node.left);
            printPostOrder(node.right);
            System.out.println("  PostOrder Traversed " + node.data);
        }
    }
    private int countNodes(Node r) {
        if(r == null)
            return 0;
        else {
            int count = 1;
            count += countNodes(r.left);
            count += countNodes(r.right);
            return count;
        }
    }
    private boolean search(Node r, int val) {
        if(r.data == val)
            return true;
        if(r.left != null){
            if(search(r.left, val))
                return true;
        }
        if(r.right != null){
            if(search(r.right, val))
                return true;
        }
        return false;         
    }

    boolean identicalTrees(Node root1, Node root2) {        
        if(root1 == null && root2 == null)
            return true;

        if(root1 != null && root2 != null) 
            return (
                    root1.data == root2.data && 
                    identicalTrees(root1.left, root2.left) && 
                    identicalTrees(root1.right, root2.right)
                 );        
        return false;
    }
}

//Output
Building tree with root value 50
  Inserted 30 to left of 50
  Inserted 20 to left of 30
  Inserted 40 to right of 30
  Inserted 70 to right of 50
  Inserted 60 to left of 70
  Inserted 80 to right of 70

Traversing Tree InOrder
  InOrder Traversed 20
  InOrder Traversed 30
  InOrder Traversed 40
  InOrder Traversed 50
  InOrder Traversed 60
  InOrder Traversed 70
  InOrder Traversed 80

Traversing Tree PreOrder
  PreOrder Traversed 50
  PreOrder Traversed 30
  PreOrder Traversed 20
  PreOrder Traversed 40
  PreOrder Traversed 70
  PreOrder Traversed 60
  PreOrder Traversed 80

Traversing Tree PostOrder
  PostOrder Traversed 20
  PostOrder Traversed 40
  PostOrder Traversed 30
  PostOrder Traversed 60
  PostOrder Traversed 80
  PostOrder Traversed 70
  PostOrder Traversed 50

Total Node Count: 7
Search Node 60: true


Properties:
1) The maximum number of nodes at level ‘L’ of a binary tree is 2 Power(L-1). Root is always at Level 1. Hence only 1 Node at Root. 
Max Node at Level 3 are 4. Here 20, 40, 60, 80 are at level 3. Here level is number of nodes on path from root to the node (including root and node). 

2) Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1. Here height of a tree is maximum number of nodes on root to leaf path. 
Height of a leaf node is considered as 1.

Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Above all images are full binary tree.
A degenerate (or pathological) tree: A Tree where every internal node has one child. Such trees are performance-wise same as linked list.