Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Deletion of node from binary search tree in java

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 83
    Comment on it

    Like a linked list we can also delete a node from binary search tree. This operation perform O(log(n)) time complexity.

    Here is an example of deletion :

    private TreeNode delete(TreeNode rootNode, int k)
    
    {
    // create a node to store temp data
        TreeNode node, node2, n;
    
        if (root.getValue() == k)
    
        {
    // create both left and right node
    
            TreeNode leftNode, rightNode;
    
            leftNode = root.getLeftNode();
    
            rightNode = root.getRightNode();
    
    // return null if its last node or leaf
            if (leftNode == null && rightNode == null)
    
                return null;
    
            else if (leftNode == null)
    
            {
    
                node = rightNode;
    
                return node;
    
            }
    
            else if (rightNode == null)
    
            {
    
                node = leftNode;
    
                return node;
    
            }
    
            else
    
            {
    
                node2 = rightNode;
    
                node = rightNode;
    
                while (node.getLeftNode() != null)
    
                    node = node.getLeftNode();
    
                node.setLeftNode(leftNode);
    
                return node2;
    
            }
    
        }
    
    // traverse to correct node by checking node value, if vallue is greater than //current node then go right otherwise go left.
    
        if (k < root.getValue())
    
        {
    
            n = delete(root.getLeftNode(), k);
    
            root.setLeftNode(n);
    
        }
    
        else
    
        {
    
    
            n = delete(root.getRightNode(), k);
    
            root.setRightNode(n);
    
        }
    
        return root;
    
    }

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: