Binary Search Trees

How to create a Node ?

class Node{
int data;
Node left;
Node right;

public Node(data){
this.data = data;
}

}

How to create a Binary Search Tree?

public class BinaryTree{
Node root;

public void insert(int data){
root = insertRec(root,data);
}

public Node insertRec(Node root, int data){
if(root == null){
root = new Node(data);
} else if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
}

How to Traverse a BST (DFS)?

public void inOrder(){
inOrderRec(root);
}

public void inOrderRec(Node root){
if(root != null){
inOrderRec(root.left);
System.out.print(root.data + " ");
inOrderRec(root.right);
}
}

BFS

public static void levelOrder(Node root) {
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    q.add(null);

    while (!q.isEmpty()) {
        Node currNode = q.remove();
        if (currNode == null) {
            System.out.println();
            if (q.isEmpty()) {
                break;
            }
        } else {
            System.out.print(currNode.data + " ");
            if (currNode.left != null) {
                q.add(currNode.left);
            }
            if (currNode.right != null) {
                q.add(currNode.right);
            }
        }
    }
}

Searching in BST ?

public Node search(int key){
return searchRec(root,data);
}

public Node searchRec(Node root, int key){
if(root == null || root.data == key){
return root;
}
if(root.data < key){
return searchRec(root.right, key);
}
return searchRec(root.left, key);
}

Deletion of Node

public static Node delete(Node root, int val) {
    if (root == null) {
        return null;
    }

    if (root.data > val) {
        root.left = delete(root.left, val);
    } else if (root.data < val) {
        root.right = delete(root.right, val);
    } else {
        // Case 1 - leaf node
        if (root.left == null && root.right == null) {
            return null;
        }
        // Case 2 - with single child
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        // Case 3 - node with two children
        Node IS = inorderSuccessor(root.right);
        root.data = IS.data;
        root.right = delete(root.right, IS.data);
    }
    return root;
}

public static Node inorderSuccessor(Node root) {
    while (root.left != null) {
        root = root.left;
    }
    return root;
}