Insert and delete in binary tree

Reference

import java.util.ArrayDeque;

class BinaryTree {
    private static Node root;
    
    static Node insertRecursive(Node current, Node previous, int data) {
        if(current == null) {
            Node node = new Node(data);
            if(previous == null) {
                // it's first node in tree 
                return node;
            } else if(data < previous.data) {
                // insert into left child 
                previous.left = node;
            } else {
                previous.right = node;
            }
            return previous;
        }
        if(data < current.data) {
            return insertRecursive(current.left, current, data);
        } 
        return insertRecursive(current.right, current, data);
    }
    
    static Node insertRecursive2(Node current, int data) {
        if(current == null) {
            return new Node(data);
        }
        if(data < current.data) {
             current.left = insertRecursive2(current.left, data);
        } else if(data > current.data) {
            current.right = insertRecursive2(current.right, data);
        }
        return current;
    }
    
    static Node insert(Node node, int data) {
        Node newNode = new Node(data);
        // if tree is empty
        if(node == null) {
            return newNode;
        }
        Node previous, current;
        current = previous = node;
        // iterate thorugh tree until don't find element or reach to end 
        while(current != null) {
            if(current.data == data) {
                // data exists in the tree 
                return node;
            }
            previous = current;
            current = data < current.data ? current.left : current.right;
        }
        if(data < previous.data) {
            previous.left = newNode;
        } else {
            previous.right = newNode;
        }
        return node;
    }
    
    // TODO
    static Node delete(Node node, int data) {
        /* Case 1: Base Case: If the tree is empty */
        if(node == null) {
            return null;
        } 
        
        /* Otherwise, recur down the tree */
        if(data < node.data) {
            node.left = delete(node.left, data);
            return node;
        } else if(data > node.data) {
            node.right = delete(node.right, data);
            return node;
        } 
        // Case 2: node with only one child or no child
        else if (node.left == null) {
            return node.right;
        } else if (node.right == null) {
            return node.left;
        }else {
            int nodeData = node.data;
            // Case 3: 
            // we found the key, delete it. We can use inorder predecessor or inorder 
            // successor to replace this node to reference it's sub trees
            // we are deciding based on height of left or right sub tree for chosing inorder 
            // predecessor or successor
            Node inorderPredOrSucc = null;
            if(height(node.left) > height(node.right)) {
                inorderPredOrSucc = inorderPredecessor(node.left);
                node.data = inorderPredOrSucc.data;
                node.left = delete(node.left, inorderPredOrSucc.data);
            } else {
                inorderPredOrSucc = inorderSuccessor(node.right);
                node.data = inorderPredOrSucc.data;
                node.right = delete(node.right, inorderPredOrSucc.data);
            }
        }
        return node;
    }
    
    static int height(Node node) {
        if(node == null) {
            return 0;
        }
        int lHeight = height(node.left);
        int rHeight = height(node.right);
        return (lHeight > rHeight ? lHeight : rHeight) + 1;
    }
    
    static Node inorderPredecessor(Node node) {
        while(node != null && node.right != null) {
            node = node.right;
        }
        return node;
    }
    
    static Node inorderSuccessor(Node node) {
        while(node != null && node.left != null) {
            node = node.left;
        }
        return node;
    }
    
    static void preOrderTraversal(Node node) {
        if(node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
    
	public static void main (String[] args) {
	    // insert operations
	    int[] data = new int[] {9, 150, 5, 200, 16, 80, 12, 30, 6, 
	    90, 15, 50, 20, 160, 8, 120, 3, 60};
	    // root = insertRecursive2(root, null, data[0]);
	    root = insertRecursive2(null, data[0]);
	    for(int i = 1; i < data.length; i++) {
	        // insertRecursive2(root, null, data[i]);
	        insertRecursive2(root, data[i]);
	    }
	    
	    System.out.println("In order traversal :");
	    preOrderTraversal(root);
	    
	    // delete operations
	    for(int i = 0; i < 10; i++) {
	        delete(root, data[i]);
	    }
	    System.out.println("\nPre order traversal after deleting 10 nodes : ");
	    preOrderTraversal(root);
	}
	
	private static class Node {
	    Node left;
	    int data;
	    Node right;
	    public Node(int data) {
	        this.data = data;
	    }
	}
}

Output
In order traversal :
9 5 3 6 8 150 16 12 15 80 30 20 50 60 90 120 200 160 
Pre order traversal after deleting 10 nodes : 
15 8 3 120 20 60 50 160 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance