Dictionary operations on a Binary Search Tree data structure?

Question

today I tried to code all the dictionary operations such as Search, Successor, Predecessor, Minimum, Maximum, Insert, Delete etc. for a Binary Search Tree data structure using the Java programming language. I would be grateful to you guys if you can review my code and suggest me some cool tricks as to how to optimize my code as well. Also it would be great if you could take a close look at my "deleteNode" method implementation and verify if it works correctly and handles all the cases or not.

// this class is used to represent the structure of a Binary Search Tree node
class BSTNode {
    private String key;
    private BSTNode parent;
    private BSTNode leftChild;
    private BSTNode rightChild;

    public String getKey() {
        return key;
    }
    public void setKey(String key) {
        this.key = key;
    }

    public BSTNode getParent() {
        return parent;
    }
    public void setParent(BSTNode parent) {
        this.parent = parent;
    }

    public BSTNode getLeftChild() {
        return leftChild;
    }
    public void setLeftChild(BSTNode leftChild) {
        this.leftChild = leftChild;
    }

    public BSTNode getRightChild() {
        return rightChild;
    }
    public void setRightChild(BSTNode rightChild) {
        this.rightChild = rightChild;
    }
}

// this class provides the API for a Binary Search Tree implementation
class BSTree {
    private BSTNode root; // this field refers to the root node of the Binary Search Tree

    // this is the constructor for the Binary Search Tree class
    public BSTree() { this.root = null; }
    public void setRoot(BSTNode root) { this.root = root; }
    public BSTNode getRoot() { return this.root; }

    // this method does the inorder tree walk on the binary search tree
    public void inorderTreeWalk(BSTNode node) {
        if(node == null) {
            return;
        }
        inorderTreeWalk(node.getLeftChild());
        System.out.print(node.getKey() + " ");
        inorderTreeWalk(node.getRightChild());
    }

    // this method does the pre-order tree walk on the binary search tree
    public void preorderTreeWalk(BSTNode node) {
        if(node == null) {
            return;
        }
        System.out.print(node.getKey() + " ");
        preorderTreeWalk(node.getLeftChild());
        preorderTreeWalk(node.getRightChild());
    }

    // this method does the post-order tree walk on the binary search tree
    public void postorderTreeWalk(BSTNode node) {
        if(node == null) {
            return;
        }
        postorderTreeWalk(node.getLeftChild());
        postorderTreeWalk(node.getRightChild());
        System.out.print(node.getKey() + " ");
    }

    // this method finds the node with the minimum key value in the Binary Search Tree
    public BSTNode findMinimum() {
        BSTNode temp = this.root;
        while(temp.getLeftChild() != null) {
            temp = temp.getLeftChild();
        }
        return temp;
    }

    // this method finds the node with the maximum key value in the Binary Search Tree
    public BSTNode findMaximum() {
        BSTNode temp = this.root;
        while (temp.getRightChild() != null) {
            temp = temp.getRightChild();
        }
        return temp;
    }

    // this method is used to search the Binary Search Tree for a node with the value passed in the parameter
    public BSTNode searchNode(String key) {
        BSTNode temp = this.root;
        while(temp != null && !temp.getKey().equals(key)) {
            if(key.compareTo(temp.getKey()) <= 0) {
                temp = temp.getLeftChild();
            } else {
                temp = temp.getRightChild();
            }
        }
        return temp;
    }

    // this is a private method that is useful in finding the successor of a node passed to the method
    private BSTNode helpFindSuccessor(BSTNode node) {
        if(node == null) {
            return null;
        }
        while(node.getLeftChild() != null) {
            node = node.getLeftChild();
        }
        return node;
    }

    // this method is used to find the successor node of the node with the given input key
    public BSTNode getSuccessor(String key) {
        BSTNode node = searchNode(key);
        if(node == null) {
            return null;
        }
        if(node.getRightChild() != null) {
            return helpFindSuccessor(node.getRightChild());
        }
        BSTNode successorNode = node.getParent();
        while(successorNode != null && successorNode.getLeftChild() != node) {
            node = successorNode;
            successorNode = successorNode.getParent();
        }
        return successorNode;
    }

    // this private method helps us in find the predecessor node in the left subtree of a binary search tree
    private BSTNode helpFindPredecessor(BSTNode node) {
        if(node == null) {
            return null;
        }
        while(node.getRightChild() != null) {
            node = node.getRightChild();
        }
        return node;
    }

    // this method is used to find the predecessor node of the node with the given input key
    public BSTNode getPredecessor(String key) {
        BSTNode node = searchNode(key);
        if(node == null) {
            return null;
        }
        if(node.getLeftChild() != null) {
            return helpFindPredecessor(node.getLeftChild());
        }
        BSTNode predecessorNode = node.getParent();
        while(predecessorNode != null && node != predecessorNode.getRightChild()) {
            node = predecessorNode;
            predecessorNode = predecessorNode.getParent();
        }
        return predecessorNode;
    }

    // this method inserts a node with a given value in the Binary Search Tree
    public void insertNode(String value) {
        // allocate a new node object for the key that needs to be inserted in the Binary Search Tree
        BSTNode node = new BSTNode();
        node.setKey(value);
        node.setParent(null);
        node.setLeftChild(null);
        node.setRightChild(null);

        // if the Binary Search Tree is initially empty then we make the new node to be the root of the Binary Search Tree
        if(this.root == null) {
            this.root = node;
        } else {
            BSTNode parentNode = null;
            BSTNode temp = this.root;
            while(temp != null) {
                parentNode = temp;
                int compareValue = node.getKey().compareTo(temp.getKey());
                if(compareValue <= 0) {
                    temp = temp.getLeftChild();
                } else {
                    temp = temp.getRightChild();
                }
            }

            // set the new node's parent to be the parentNode object that was set in the loop
            node.setParent(parentNode);
            if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
                parentNode.setLeftChild(node);
            } else {
                parentNode.setRightChild(node);
            }
        }
    }

    // this method is used to delete a node from the Binary Search Tree
    public void deleteNode(BSTNode node) {
        // check if the node to be deleted is a valid reference, if its an invalid reference then we don't need to do anything at all
        if(node == null) {
            return;
        }

        // Case-1 : If the node to be deleted has no child references at all
        if(node.getLeftChild() == null && node.getRightChild() == null) {
            BSTNode parentNode = node.getParent();
            // if the node to be deleted is the root node
            if(parentNode == null) {
                this.root = null;
            } else if (parentNode.getLeftChild() == node) {
                parentNode.setLeftChild(null );
            } else {
                parentNode.setRightChild(null);
            }
            node.setParent(null);
        }

        // Case-2 : If the node to be deleted has one node as its child node
        if(node.getLeftChild() != null && node.getRightChild() == null) {
            BSTNode parentNode = node.getParent();
            // if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
            if(parentNode == null) {
                this.root = node.getLeftChild();
            } else {
                // if the node to be deleted is the left child of its parent node
                if(parentNode.getLeftChild() == node) {
                    parentNode.setLeftChild(node.getLeftChild());
                } else {
                    parentNode.setRightChild(node.getLeftChild());
                }
            }
            node.getLeftChild().setParent(parentNode);
            node.setParent(null);
            node.setLeftChild(null);
        }

        if(node.getLeftChild() == null && node.getRightChild() != null) {
            BSTNode parentNode = node.getParent();
            // if the node to be deleted is the root node and it has a right child
            if(parentNode == null) {
                this.root = node.getRightChild();
            } else {
                // if the node to be deleted is the left child of its parent node
                if(parentNode.getLeftChild() == node) {
                    parentNode.setLeftChild(node.getRightChild());
                } else {
                    parentNode.setRightChild(node.getRightChild());
                }
            }
            node.getRightChild().setParent(parentNode);
            node.setParent(null);
            node.setRightChild(null);
        }

        // Case-3 : if the node to be deleted has both a left and a right child
        if(node.getLeftChild() != null && node.getRightChild() != null) {
            BSTNode parentNode = node.getParent();

            // first we get the successor of the node in the Binary Search Tree
            BSTNode successorNode = getSuccessor(node.getKey());
            BSTNode successorParent = successorNode.getParent();
            BSTNode successorRightChild = successorNode.getRightChild();

            // if the successor node doesn't have any right child, it obviously doesn't have any left child as its the successor node
            if(successorRightChild == null) {
                node.setKey(successorNode.getKey());
                if(successorParent.getRightChild() == successorNode) {
                    successorParent.setRightChild(null);
                } else {
                    successorParent.setLeftChild(null);
                }
                return;
            } else {
                node.setKey(successorNode.getKey());
                if(successorParent.getRightChild() == successorNode) {
                    successorParent.setRightChild(successorRightChild);
                } else {
                    successorParent.setLeftChild(successorRightChild);
                }
            }
            successorRightChild.setParent(successorParent);
            successorNode.setParent(null);
            successorNode.setLeftChild(null);
            successorNode.setRightChild(null);
        }
    }
}

public class BinarySearchTree {
    public static void main(String[] args) {
        BSTree tree = new BSTree();
        tree.insertNode("D");
        tree.insertNode("B");
        tree.insertNode("C");
        tree.insertNode("A");
        tree.insertNode("F");
        tree.insertNode("G");
        // tree.insertNode("E");
        tree.insertNode("I");
        tree.insertNode("H");
        tree.insertNode("J");
        tree.insertNode("L");
        tree.insertNode("K");
        System.out.println("Inorder Tree Walk : ");
        tree.inorderTreeWalk(tree.getRoot());
        System.out.println();
        System.out.println("Preorder Tree Walk : ");
        tree.preorderTreeWalk(tree.getRoot());
        System.out.println();
        System.out.println("Postorder Tree Walk : ");
        tree.postorderTreeWalk(tree.getRoot());
        System.out.println();
        System.out.println("Node with the minimum key in the Binary Search Tree : " + tree.findMinimum().getKey());
        System.out.println("Node with the maximum key in the Binary Search Tree : " + tree.findMaximum().getKey());
        tree.deleteNode(tree.searchNode("D"));
        System.out.println("Inorder Tree Walk after deletion of node D : ");
        tree.inorderTreeWalk(tree.getRoot());
        System.out.println();
    }
}

Answer 1

In deleteNode, you get successorNodes like so:

        BSTNode successorNode = getSuccessor(node.getKey());

So you have a node reference, then you get the key, and pass this into the method.

Then, in the method...

public BSTNode getSuccessor(String key) {
    BSTNode node = searchNode(key);

The first thing you do is pass it on to searchNode, which does a binary search to find the same node!

So what you could do is add overloading, where you convert the original method into a helper function:

// this method is used to find the successor node of the node with the given input key
public BSTNode getSuccessor(String key) {
    return getSuccessor(searchNode(key));
}

// this method is used to find the successor node of the node
public BSTNode getSuccessor(BSTNode node) {
    if(node == null) {
        return null;
    }
    if(node.getRightChild() != null) {
        return helpFindSuccessor(node.getRightChild());
    }
    BSTNode successorNode = node.getParent();
    while(successorNode != null && successorNode.getLeftChild() != node) {
        node = successorNode;
        successorNode = successorNode.getParent();
    }
    return successorNode;
}

The same goes for getPredecessor.

---

    while(temp != null && !temp.getKey().equals(key)) {
        if(key.compareTo(temp.getKey()) <= 0) {
            temp = temp.getLeftChild();
        } else {
            temp = temp.getRightChild();
        }
    }

            int compareValue = node.getKey().compareTo(temp.getKey());
            if(compareValue <= 0) {
                temp = temp.getLeftChild();
            } else {
                temp = temp.getRightChild();
            }

        if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
            parentNode.setLeftChild(node);
        } else {
            parentNode.setRightChild(node);
        }

Here you do (three snippets) seemingly the same thing three times. Compare a key to the key of a node, and, depending on that, get/set a child. Is it possible to convert this to something the node could do?

---

    if(node.getLeftChild() != null && node.getRightChild() == null) {
        BSTNode parentNode = node.getParent();
        // if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
        if(parentNode == null) {
            this.root = node.getLeftChild();
        } else {
            // if the node to be deleted is the left child of its parent node
            if(parentNode.getLeftChild() == node) {
                parentNode.setLeftChild(node.getLeftChild());
            } else {
                parentNode.setRightChild(node.getLeftChild());
            }
        }
        node.getLeftChild().setParent(parentNode);
        node.setParent(null);
        node.setLeftChild(null);
    }

    if(node.getLeftChild() == null && node.getRightChild() != null) {
        BSTNode parentNode = node.getParent();
        // if the node to be deleted is the root node and it has a right child
        if(parentNode == null) {
            this.root = node.getRightChild();
        } else {
            // if the node to be deleted is the left child of its parent node
            if(parentNode.getLeftChild() == node) {
                parentNode.setLeftChild(node.getRightChild());
            } else {
                parentNode.setRightChild(node.getRightChild());
            }
        }
        node.getRightChild().setParent(parentNode);
        node.setParent(null);
        node.setRightChild(null);
    }

These could be combined into this:

if((node.getLeftChild() == null) != (node.getRightChild() == null)) {
    BSTNode parentNode = node.getParent();
    BSTNode childNode = node.getLeftChild();
    if(childNode == null){
        childNode = node.getRightChild();
    }
    // if the node to be deleted is the root node and it has a right child
    if(parentNode == null) {
        this.root = childNode;
    } else if(parentNode.getLeftChild() == node) {
        parentNode.setLeftChild(childNode);
    } else {
        parentNode.setRightChild(childNode);
    }
    childNode.setParent(parentNode);
    node.setParent(null);
    node.setRightChild(null);
    node.setLeftChild(null);
}

Lastly, for deleteNode, you have case 1 left == null && right == null, case 2 left == null XOR right == null and case 3 left != null && right != null. You should use else-ifs here, because if 1 and 2 don't match, 3 does.

Answer 2

(noticed Pimgd's answer just recently - there are common points)

• document. In the source code: everything else will get seperated/not updated (which neither means other documentation is not needed nor that documentation in source code will automagically stay up to date - with the possible exception of literal programming)

• when implementing multiple related operations, it is beneficial to have an interface for them. E.g. what shall happen when a key to be inserted is already present? I tried extracting one from your source code, most striking was no lookup (didn't call it Dictionary because of that):

  /** Operations of ordered collections */
  interface OrderedCollection<K extends Comparable<K>> {
   /** Inserts {@code key}.
    * @return previous value of {@code key}, or {@code null} if not found */
      K insert(K key);
   /** Deletes {@code key}.
    * @return previous value of {@code key}, or {@code null} if not found */
      K delete(K key);
  
   /** Searches for {@code key}.
    * @return value for {@code key}, or {@code null} if not found */
      K find(K key);
  
   /** Get the predecessor of the value for {@code key}, if any
    * @return the predecessor of the value for {@code key}, if any */
      public K getPredecessor(K key);
   /** Gets the successor of the value for {@code key}, if any
    * @return the successor of the value for {@code key}, if any */
      public K getSuccessor(K key);
  
   /** @return Minimum {@code key} in collection, or {@code null} if empty */
      K minimum();
   /** @return Maximum {@code key} in collection, or {@code null} if empty */
      K maximum();
  }
  

  – consider extending java.util.Collection or similar
  – specifying insert(key) to replace the previous value would make this less similar to java.util.Set<E>. java.util.HashMap<K, V> specifies put and putIfAbsent to have both.
  – note no mention of node: that would be tree, not dictionary or OrderedCollection.
  – you could define interfaces for node and tree - I tried that and might add it together with other (excessive) finger exercises to the end of this answer.
  – use tools: javadoc, for one
  – I tried adding /** Invokes {@code visit} for every {@code key}. */ void walk(java.util.function.Consumer<K> visit); - looked off.

• talking about nodes and trees, I get confused more often than not about what constitutes a tree operation in contrast to a node operation.
  – if you specify structurally modifying operations such as insert&delete to return the new root, I don't see need for parent (& handling thereof) - delete() gets much simpler.

• avoid code duplication/multiplication/cut&paste

Finger exercises (WiP), with much less than due commenting, QA (do as I say, don't do as I do…), many more casts than pretty (extensive type hierarchies without extensive method overriding), …:

package net.reserves.human.coder.greybeard.sandbox;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.function.Consumer;
import java.util.stream.Stream;

/** Operations of nodes of (not necessarily binary) trees. */
interface TreeNode {
    static class Util { // didn't find a way to hide this
        static void visitChildren(final TreeNode node,
            final Consumer<TreeNode> pre,
            final Consumer<TreeNode> between,
            final Consumer<TreeNode> post) {
            Consumer<TreeNode> before = pre;
            for (TreeNode child : node.children()) {
                if (null != before)
                    before.accept(node);
                if (null != child)
                    visitChildren(child, pre, between, post);
                before = between;
            }
            if (null != post)
                post.accept(node);
        }
    }
 /** Applies {@code visit} to {@code this}, followed by
  * a @{@code preorderTreeWalk(visit)} of all descendants, if any. */
    default void preorderWalk(Consumer<TreeNode> visit) {
        Util.visitChildren(this, visit, null, null);
    }
 /** Does a @{@code preorderTreeWalk(visit)} of all descendants, if any,
  * finally applying {@code visit} to {@code this}. */
    default void postorderWalk(Consumer<TreeNode> visit) {
        Util.visitChildren(this, null, null, visit);
    }

    Iterable<TreeNode> children();
}
interface BinTreeNode extends TreeNode {
    BinTreeNode getLeftChild();
    BinTreeNode getRightChild();

 /** Does an @{@code inorderWalk(visit)} of the left subtree, if present,
  * applies {@code visit} to {@code this}, concluding with
  * a @{@code inorderWalk(visit)} of the right subtree, if any.
  * @param visit */
    default void inorderWalk(Consumer<TreeNode> visit) {
        Util.visitChildren(this, null, visit, null);
    }
}
class BTNode implements BinTreeNode {
    BinTreeNode
        leftChild,
        rightChild;
    public BinTreeNode getLeftChild() { return leftChild; }
    public BinTreeNode getRightChild() { return rightChild; }

    @Override
    public Iterable<TreeNode> children() {
        return Arrays.asList(getLeftChild(), getRightChild());
    }
}
interface MutableBinTreeNode  {
    void setLeftChild(BinTreeNode left);
    void setRightChild(BinTreeNode right);
}
class MutableBTNode extends BTNode
    implements MutableBinTreeNode {
    public void setLeftChild(BinTreeNode left) { leftChild = left; }
    public void setRightChild(BinTreeNode right) { rightChild = right; }
}
// more hierarchical garlic like above follows "the BSTree class"

public class BinarySearchTree {
    public static void main(String[] args) throws Exception {
        BSTree<String> tree = new BSTree<>();
        String [] inserts = new String[] { "D", "B", "C", "A", "F", "G",
        // tree.insertNode(
        //  "E",
            "I", "H", "J", "L", "K"};
        System.out.println("goint to insert "
            + Arrays.deepToString(inserts));
        for (String s : inserts) {
            tree.insert(s);
        }
        Object[] treeWalks = Stream.of(
            tree.getClass().getDeclaredMethods())
            .filter(method -> method.getName().endsWith("Walk"))
            .toArray();
        Object[] nullOnly = { null };
        for (Object walk : treeWalks) {
            Method consumer = (Method) walk;
            System.out.println(consumer.getName());
            consumer.invoke(tree, nullOnly);
            System.out.println();
        }
        tree.delete("D");
        System.out.println("Inorder Tree Walk after deletion of node D : ");
        tree.inorderWalk(null);
        System.out.println();
    }
}

// this class provides the API for a Binary Search Tree implementation
class BSTree<K extends Comparable<K>>
    implements Ordered.Collection<K>, BinaryTree {
    private BSTNode<K> root; // this field refers to the root node of the
                            // Binary Search Tree

    // this is the constructor for the Binary Search Tree class
    public BSTree() {
        this.root = null;
    }

    public void setRoot(BSTNode<K> root) {
        this.root = root;
    }

    public BSTNode<K> getRoot() {
        return this.root;
    }

    static void defaultVisit(TreeNode node) {
        @SuppressWarnings("rawtypes")
        BinSearchTreeNode bstNode = (BinSearchTreeNode) node;
        System.out.append(String.valueOf(bstNode.getKey())).append(' ');
    }
    Consumer<TreeNode> defaultVisit(Consumer<TreeNode> visit) {
        return null == visit ? BSTree::defaultVisit : visit;
    }
 /** Does an {@code inorderWalk(visit)} of root, if not empty.
  * @param visit */
    @Override
    public void inorderWalk(Consumer<TreeNode> visit) {
        if (root == null) {
            return;
        }
        root.inorderWalk(defaultVisit(visit));
    }

 /** Applies {@code visit} to this tree's root, followed by
  * a @{@code preorderTreeWalk(visit)} of all descendants, if any. */
    public void preorderWalk(Consumer<TreeNode> visit) {
        if (root == null) {
            return;
        }
        root.preorderWalk(defaultVisit(visit));
    }

    // this method does the post-order tree walk on the binary search
    // tree
    /* (non-Javadoc)
     * @see net.reserves.human.coder.greybeard.sandbox.SearchTree#postorderTreeWalk(net.reserves.human.coder.greybeard.sandbox.BinSearchTreeNode)
     */
    public void postorderWalk(Consumer<TreeNode> visit) {
        if (root == null) {
            return;
        }
        root.postorderWalk(defaultVisit(visit));
    }

    // this method finds the node with the minimum key value in the
    // Binary Search Tree
    /* (non-Javadoc)
     * @see net.reserves.human.coder.greybeard.sandbox.Ordered.Tree#minimum()
     */
    @Override
    public K minimum() {
        if (null == root)
            return null;
        BSTNode<K> temp = this.root;
        while (temp.getLeftChild() != null) {
            temp = (BSTNode<K>) temp.getLeftChild();
        }
        return temp.getKey();
    }

    // this method finds the node with the maximum key value in the
    // Binary Search Tree
    /* (non-Javadoc)
     * @see net.reserves.human.coder.greybeard.sandbox.Ordered.Collection#maximum()
     */
    @Override
    public K maximum() {
        if (null == root)
            return null;
        BSTNode<K> temp = this.root;
        while (temp.getRightChild() != null) {
            temp = (BSTNode<K>) temp.getRightChild();
        }
        return temp.getKey();
    }

    /* (non-Java doc)
     *  @see net.reserves.human.coder.greybeard.sandbox.Ordered.Collection#find(K) */
    @Override
    public K find(K key) {
        BinSearchTreeNode<K> temp = root;
        K nodeKey;
        while (temp != null
               && key != (nodeKey = temp.getKey())) //.equals(key))
        {
            final int comp = key.compareTo(nodeKey);
        // there is no guarantee that compareto() is consistent with equals()
            if (0 == comp)
                return temp.getKey();
            temp = comp < 0
                ? temp.getLeftChild()
                : temp.getRightChild();
        }
        return null;
    }
    /* (non-Javadoc)
     *  @see net.reserves.human.coder.greybeard.sandbox.Ordered.Collection#find(K) */
    public BinSearchTreeNode<K> findNode(K key) {
        BinSearchTreeNode<K> temp = root;
        K nodeKey;
        while (temp != null) //.equals(key))
        {
            if (key == (nodeKey = temp.getKey())
                || key.equals(nodeKey))
                return temp;
            final int comp = key.compareTo(nodeKey);
        // there is no guarantee that compareto() is consistent with equals()
            if (0 == comp)
                return temp;
            temp = comp < 0
                ? temp.getLeftChild()
                : temp.getRightChild();
        }
        return null;
    }

    // this is a private method that is useful in finding the successor
    // of a node passed to the method
    private BSTNode<K> helpFindSuccessor(BinSearchTreeNode<K> node) {
        if (node == null) {
            return null;
        }
        while (node.getLeftChild() != null) {
            node = node.getLeftChild();
        }
        return (BSTNode<K>) node;
    }

    // this method is used to find the successor node of the node with
    // the given input key
    /* (non-Javadoc)
     * @see net.reserves.human.coder.greybeard.sandbox.SearchTree#getSuccessor(K)
     */
    @Override
    public K getSuccessor(K key) {
        ParentedBinSearchTreeNode<K>
            node = (ParentedBinSearchTreeNode<K>) findNode(key);
        return getSuccessor(node).getKey();
    }
    BinSearchTreeNode<K> getSuccessor(ParentedBinSearchTreeNode<K> node) {
        if (node == null) {
            return null;
        }
        if (node.getRightChild() != null) {
            return helpFindSuccessor(node.getRightChild());
        }
        for (ParentedBinSearchTreeNode<K> successorNode ;
             null != (successorNode = node.getParent()) ; ) {
            if (successorNode.getLeftChild() == node)
                return successorNode;
        }
        return null;
    }
 // symmetrical
    private BSTNode<K> helpFindPredecessor(BinSearchTreeNode<K> node) {
        return null;
    }
    @Override
    public K getPredecessor(K key) { return null; }

 /** Inserts {@code key}.
  * @return previous value of {@code key}, or {@code null} if not found */
    @Override
    public K insert(K value) {
        // allocate a new node object for the key that needs to be
        // inserted in the Binary Search Tree
        BSTNode<K> node = new BSTNode<K>();
        node.setKey(value);
//      node.setParent(null); members always get initialised

        // if the Binary Search Tree is initially empty then we make the
        // new node to be the root of the Binary Search Tree
        if (root == null) {
            root = node;
            return null;
        }

        BinSearchTreeNode<K> parentNode = null;
        int compareValue = 0;
        for (BinSearchTreeNode<K> temp = root ;
             temp != null ; ) {
            K tempKey = temp.getKey();
            if (0 == (compareValue = value.compareTo(tempKey))) {
                return tempKey;
            }
            parentNode = temp;
            temp = compareValue < 0
                ? temp.getLeftChild() : temp.getRightChild();
        }

        // set the new node's parent to be the parentNode object
        // that was set in the loop
        node.setParent((ParentedBinTreeNode) parentNode);
        if (compareValue < 0) {
            ((MutableBinTreeNode) parentNode).setLeftChild(node);
        } else { // (0 < compareValue)
            ((MutableBinTreeNode) parentNode).setRightChild(node);
        }
        return null;
    }
    // this method is used to delete a node from the Binary Search Tree
    public K delete(K key) {
        BinSearchTreeNode<K> node = findNode(key);
        deleteNode((BSTNode<K>) node);
        return node.getKey();
    }

 /** Deletes {@code key}.
  * @return previous value of {@code key}, or {@code null} if not found */
    public void deleteNode(BSTNode<K> node) {
        // check if the node to be deleted is a valid reference, if its
        // an invalid reference then we don't need to do anything at all
        if (node == null) {
            return;
        }

        // Case-3 : if the node to be deleted
        //  has both a left and a right child
        if (node.getLeftChild() != null
            && node.getRightChild() != null) {
        // first we get the successor of the node in the Binary Search Tree
            final BSTNode<K>
                successorNode = (BSTNode<K>) getSuccessor(node),
                successorParent = (BSTNode<K>) successorNode.getParent(),
                successorRightChild = (BSTNode<K>) successorNode.getRightChild();

            // if the successor node doesn't have any right child,
            // it obviously doesn't have any left child
            // as it's the successor node
            node.setKey(successorNode.getKey());
            if (successorParent.getRightChild() == successorNode) {
                successorParent.setRightChild(successorRightChild);
            } else {
                successorParent.setLeftChild(successorRightChild);
            }
            if (null != successorRightChild) {
                successorRightChild.setParent(successorParent);
            // What for? Trying to help GC is obsolete, at best
                successorNode.setParent(null);
                successorNode.setLeftChild(null);
                successorNode.setRightChild(null);
            }
            return;
        }
        final BSTNode<K> parentNode = (BSTNode<K>) node.getParent();
        BSTNode<K> replacement = null;

    // Case-2 : The node to be deleted could have one more child
        if (node.getLeftChild() != null) {
            replacement = (BSTNode<K>) node.getLeftChild();
        } else if (node.getRightChild() != null) {
            replacement = (BSTNode<K>) node.getRightChild();
        }
        if (null != replacement) {
            replacement.setParent(parentNode);
        } // else Case-1
        if (parentNode == null) {
            root = replacement;
        } else {
            // if the node to be deleted
            // is the left child of its parent node
            if (parentNode.getLeftChild() == node) {
                parentNode.setLeftChild(replacement);
            } else {
                parentNode.setRightChild(replacement);
            }
        }
    }
}


class ParentedBinTreeNode extends BTNode {
    ParentedBinTreeNode parent;
    public ParentedBinTreeNode getParent() { return parent; }
}
interface MutableParentedBinTreeNode extends MutableBinTreeNode {
    void setParent(ParentedBinTreeNode parent);
}
class MutablePBTNode extends ParentedBinTreeNode
    implements MutableParentedBinTreeNode {
    public void setLeftChild(BinTreeNode left) { leftChild = left; }
    public void setRightChild(BinTreeNode right) { rightChild = right; }
    public void setParent(ParentedBinTreeNode parent) {
        this.parent = parent;
    }
}
interface BinSearchTreeNode<K> extends BinTreeNode {
    BinSearchTreeNode<K> getLeftChild();
    BinSearchTreeNode<K> getRightChild();
    K getKey();
}
class BSTNodeImpl<K> extends BTNode
    implements BinSearchTreeNode<K> {
    K key;
    @Override
    public K getKey() { return key; }
    @Override @SuppressWarnings("unchecked")
    public BSTNodeImpl<K> getLeftChild() {
        return (BSTNodeImpl<K>) leftChild;
    }
    @Override @SuppressWarnings("unchecked")
    public BSTNodeImpl<K> getRightChild() {
        return (BSTNodeImpl<K>) rightChild;
    }
    @Override public
    String toString() { return String.valueOf(getKey()); }
}
interface MutableBinSearchTreeNode<K>  extends BinSearchTreeNode<K> {
    void setKey(K key);
}
class MutableBSTNode<K> extends BSTNodeImpl<K>
    implements MutableBinSearchTreeNode<K> {
    public void setLeftChild(MutableBSTNode<K> left) { leftChild = left; }
    public void setRightChild(MutableBSTNode<K> right) { rightChild = right; }
    @Override
    public void setKey(K key) { this.key = key; }
    @Override public
    String toString() { return String.valueOf(getKey()); }
}
interface ParentedBinSearchTreeNode<K> extends BinSearchTreeNode<K> {
    ParentedBinSearchTreeNode<K> getParent();
}
class ParentedBSTNode<K extends Comparable<K>> // this is where the fun starts 
    extends ParentedBinTreeNode
    implements ParentedBinSearchTreeNode<K> {
    K key;
    @Override
    public K getKey() { return key; }

    @Override @SuppressWarnings("unchecked")
    public ParentedBSTNode<K> getLeftChild() {
        return (ParentedBSTNode<K>) leftChild;
    }
    @Override @SuppressWarnings("unchecked")
    public ParentedBSTNode<K> getRightChild() {
        return (ParentedBSTNode<K>) rightChild;
    }
    @Override @SuppressWarnings("unchecked")
    public ParentedBSTNode<K> getParent() {
        return (ParentedBSTNode<K>) parent;
    }
}
interface MutableParentedBinSearchTreeNode<K>
    extends MutableBinSearchTreeNode<K>, MutableParentedBinTreeNode {
}
class MutableParentedBSTNode<K extends Comparable<K>> // this is where the fun starts 
    extends ParentedBSTNode<K>
    implements MutableParentedBinSearchTreeNode<K> {
    @Override
    public void setLeftChild(BinTreeNode left) { leftChild = left; }
    @Override
    public void setRightChild(BinTreeNode right) { rightChild = right; }
    @Override
    public void setKey(K key) { this.key = key; }
    @Override
    public void setParent(ParentedBinTreeNode parent) {
        this.parent = parent;
    }
    @Override public
    String toString() { return String.valueOf(getKey()); }
}

/** Binary Tree Node with a key */
class BSTNode<K extends Comparable<K>> extends MutableParentedBSTNode<K> { }

interface BinaryTree {
    // this method does the inorder tree walk on the binary search tree
    void inorderWalk(Consumer<TreeNode> visit);
}