CODEWITHSUNDEEP
javabinary-search-tree
Jack Nickolson
Jack Nickolson

Reputation: 225

Returning deleted node from binary search tree

I'm attempting to write a method that would remove node from BST by the given value and I need it to return this deleted value. I found assorted examples of recursive implementations, but because of their nature, they can't return deleted node, but rather the root. Here's what I have now 

 public TreeNode remove(TreeNode node, int data) {
        if (null == node) {
            return null;
        }
        if (data < node.st.getkey()) {
            node.left = remove(node.left, data);
        } else if (data > node.st.getkey()) {
            node.right = remove(node.right, data);
        } else { // case for equality

            if (node.left != null && node.right != null) {
                TreeNode minInRightSubTree = min(node.right);

                copyData(node , minInRightSubTree);

                node.right = remove(node.right, minInRightSubTree.st.getkey());
            } else {
                if (node.left == null && node.right == null) {
                    node = null;
                } else {// one child case
                    TreeNode deleteNode = node;
                    node = (node.left != null) ? (node.left) : (node.right);
                    deleteNode = null;
                }
            }
        }
        return node;
    }

Can I come up with some hack to make it return deleted node or should I look into iterative algorithm( and if so I would really appreciate it if you could hook me up with the link).

Upvotes: 1

Views: 715

Answers (1)

nickolay.laptev
nickolay.laptev

Reputation: 2565

You can return not just root but a pair of root and deleted node (or null if nothing was deleted). You can use Map.Entry or new class to store 2 fields (I would recommend new class since it's more descriptive). So your possible new signature will be public Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)

Upvotes: 1

Related Questions