Data Structure: Binary Tree, Part I

Binary Tree is the one of the Data Structure of Tree where it has two possible branches i.e left and right branch. Let's move on examples. This code implements Binary Tree and its operations(get, insert, add, remove)

public class BSTree< T1 extends Comparable, T2 > {
        static class Node< T1, T2> {
                T1 key;
                T2 value;
                Node< T1, T2 > left, right;
               
                Node(T1 key, T2 value) {
                        this.key = key;
                        this.value = value;
                }
        }
        private Node< T1, T2 > root = null;
       
        public boolean containsKey(T1 k) {
                Node< T1, T2> x = root;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                return true;
                        }
                        if (cmp < 0) {
                                x = x.left;
                        } else {
                                x = x.right;
                        }
                }
                return false;
        }
       
        public T2 get(T1 k) {
                Node< T1, T2> x = root;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                return x.value;
                        }
                        if (cmp < 0) {
                                x = x.left;
                        } else {
                                x = x.right;
                        }
                }
                return null;
        }
       
        public void add(T1 k, T2 v) {
                Node< T1, T2> x = root, y = null;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                x.value = v;
                                return;
                        } else {
                                y = x;
                                if (cmp < 0) {
                                        x = x.left;
                                } else {
                                        x = x.right;
                                }
                        }
                }
                Node< T1, T2> newNode = new Node< T1, T2>(k, v);
                if (y == null) {
                        root = newNode;
                } else {
                        if (k.compareTo(y.key) < 0) {
                                y.left = newNode;
                        } else {
                                y.right = newNode;
                        }
                }
        }
       
        public void remove(T1 k) {
                Node< T1, T2> x = root, y = null;
                while (x != null) {
                        int cmp = k.compareTo(x.key);
                        if (cmp == 0) {
                                break;
                        } else {
                                y = x;
                                if (cmp < 0) {
                                        x = x.left;
                                } else {
                                        x = x.right;
                                }
                        }
                }
                if (x == null) {
                        return;
                }
                if (x.right == null) {
                        if (y == null) {
                                root = x.left;
                        } else {
                                if (x == y.left) {
                                        y.left = x.left;
                                } else {
                                        y.right = x.left;
                                }
                        }
                } else {
                        Node< T1, T2> leftMost = x.right;
                        y = null;
                        while (leftMost.left != null) {
                                y = leftMost;
                                leftMost = leftMost.left;
                        }
                        if (y != null) {
                                y.left = leftMost.right;
                        } else {
                                x.right = leftMost.right;
                        }
                        x.key = leftMost.key;
                        x.value = leftMost.value;
                }
        }
}

Another one is more simple to understand.

public class BinaryTreeExample
{

    public static void main(String[] args)
    {
        new BinaryTreeExample().run();
    }

    static class Node

    {
        Node left;
        Node right;
        int value;

        public Node(int value)
        {
            this.value = value;
        }
    }

    public void run()
    {
        Node rootnode = new Node(25);
        System.out.println("Building tree with rootvalue  " + rootnode.value); 
        System.out.println("=================================");
        insert(rootnode, 11);
        insert(rootnode, 15);
        insert(rootnode, 16);
        insert(rootnode, 23);
        insert(rootnode, 79);
        System.out.println("Traversing tree in order");
        System.out.println("=================================");
        printInOrder(rootnode);

    }

    public void insert(Node node, int value)
    {
        if (value < node.value)
        {
            if (node.left != null)
            {
                insert(node.left, value);
            }
            else
            {
                System.out.println("  Inserted " + value + " to left of node " + node.value);
                node.left = new Node(value);
            }
        }
        else if (value > node.value)
        {
            if (node.right != null)
            {
                insert(node.right, value);
            }
            else
            {
                System.out.println("  Inserted " + value + "  to right of node" + node.value);
                node.right = new Node(value);
            }
        }
    }

    public void printInOrder(Node node)
    {
        if (node != null)
        {
            printInOrder(node.left);
            System.out.println("  Traversed " + node.value);
            printInOrder(node.right);
        }
    }
}

Here is using traversing method to get a sequence of branches.
Output:

Building tree with root value 25
 =================================
Inserted 11 to left of node 25
Inserted 15 to right of node 11
Inserted 16 to right of node 15
Inserted 23 to right of node 16
Inserted 79 to right of node 25
Traversing tree in order
 =================================
Traversed 11
Traversed 15
Traversed 16
Traversed 23
Traversed 25
Traversed 79