Binary Trees

What is binary trees ? it is tree data structure. It contains nodes. a top node is root. Each node contains left and right node. Left node is smaller than parent. Right node is bigger than parent.

Binary Search Tree (BST)

BST has an ability search really fast . Runtime is O(log n)

Node structure

private static class Node {
        int key;
        String value;
        private Node left;
        private Node right;

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

        public Node min() {
            if(left == null) {
                return this;
            }
            return this.left;
        }
    }

Binary structure

public class BinarySearchTree {

    private Node root;

    public void insert(int key, String value) {}

    public String find(int key) {}
    
    public String delete(int key) {}

}

How to to insert ? Using the recursion to traversal down until see the null. Go left or right by checking the key. Left down if key less than current node key.

public void insert(int key, String value) {
        this.insertItem(root, key, value);
}

private Node insertItem(Node node, int key, String value) {
    Node newNode = new Node(key, value);
    if(node == null) {
        node = newNode;
        return node;
    }
    if (key < node.key) {
        node.left = insertItem(node.left, key, value);
    } else {
        node.right = insertItem(node.right, key, value);
    }
    return node;
}

How to find ?

  
 public String find(int key) {
        Node node = find(root, key);
        return  node == null ? null : node.value;
 }
 private Node find(Node node, int key) {
        if(node == null || node.key == key) {
            return node;
        } else if(key < node.key) {
            return find(node.left, key);
        }
        else if(key > node.key) {
            return find(node.right, key);
        }
        return null;
    }

How to delete ?

• Delete node has no child
• Delete node has one child
• Delete node has 2 children

    public void delete(int key) {
        root = delete(root, key);
    }

    private Node delete(Node node, int key) {
        if(node == null) {
            return null;
        } else if(key <node.key) {
            node.left = delete(node.left, key);
        } else if(key > node.key) {
            node.right = delete(node.right, key);
        } else {
          // Case 1: No child
          if(node.left == null && node.right == null) {
              node = null;
          }
          // Case 2 : One Child
            else if ( node.left == null) {
                node = node.right;
            }
          else if ( node.right == null) {
              node = node.left;
          }
          // Case 3: Two children
          else {
              Node minRight = findMin(node.right);
              node.key = minRight.key;
              node.value = minRight.value;

              //Now go delete the node we just duplicated
              node.right = delete(node.right, node.key);
          }
        }
        return node;
    }

    private Node findMin(Node node) {
        return node.min();
    }

Binary Tree Traversal :

• Depth First Traversal
  • Inorder (Left, Root, Right)
  • Preorder (Root, Left, Right)
  • Postorder (Left, Right, Root)
• Breadth Traversal

Binary Search Tree Runtime : O (log n)

Binary Search Tree is Ordered

Binary Search Tree is recursive

Binary Search is super fast