Delete Node in a BST


  • 1
    A

    A straight forward solution for searching for the given key in a BST and deleting it.

    TreeNode deleteNode(TreeNode root, int key){
    		//General sanity check and if you ever run into a null node, just turn back
    		if(root == null)
    			return root;
    		
    		/*
    		 * Check if the given key is lesser than the root's key, if yes, go down its left subtree
    		 * else if the key is bigger than the root's key, then go down its right subtree
    		 */
    		 
    		if(key < root.val)
    			root.left = deleteNode(root.left, key);
    		else if(key > root.val)
    			root.right = deleteNode(root.right,key);
    		else{ 
    			//If you have reached the node that you're searching for, 2 conditions arise
    			
    			//1. Suppose the node has 0 or 1 children			
    			if(root.left ==null || root.right == null){
    				TreeNode temp = null;
    				
    				//If there is not left subtree, assign the right subtree to the temp
    				if(root.left == null)
    					temp = root.right;
    				else
    					temp = root.left;
    				
    				//Now rewrite the current node (which you wanted to delete) with its children
    				root = temp;
    			}else{
    				/*
    				 * 2. Suppose the node has 2 children, then travel down its right subtree and
    				 * get the next In-Order successor. Basically, get the smallest node 
    				 * in the current node's right subtree 
    				 */
    				TreeNode next = getMin(root.right);
    				
    				//Overwrite current node's key with the successor's key 
    				root.val = next.val;
    				
    				//Now delete the original successor from the right subtree
    				root.right = deleteNode(root.right, next.val);
    			}
    		}
    		return root;
    	}
    	
    	/*
    	 * Utility function to get the smallest node in a BST
    	 */
    	TreeNode getMin(TreeNode root){
    		if(root != null){
    			while(root.left != null)
    				root = root.left;
    		}
    		return root;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.