Binary search tree boolean return type-CodePudding

This is a function that add a node in my binary search tree.How can i reformat that to return true if this tree did not already contain the specified element.

private Node insertNode(Node root, Student student) {
    if (root == null) {
        root = new Node(student);
    }
    int comp;
    if (Comparator != null) {
        comp = Comparator.compare(student, root.value);
    } else {
        comp = student.compareTo(root.value);
    }

    if (comp < 0) {
        root.left = insertNode(root.left, student);
    } else if (comp > 0) {
        root.right = insertNode(root.right, student);
    }
    return root;
}

CodePudding user response：

You need to refactor this code considerably if you want this.

It may be a lot simpler to first search for the node, if it exists, return false, and if not, run this code then return true. Something like:

// Keep `insertNode`, as is, unchanged, except name it `createNode`.
// Make sure to include in its docs that it doesn't create
// if the `student` record already exists in the tree.

private boolean insertNode(Student student) {
    if (search(this.root, student)) return false;
    createNode(this.root, student);
    return true;
}

As a general rule, you almost always want 2 methods when writing recursive algorithms. The actual recursive method, which is private and has nonsense arguments, at least when looking at it from an API perspective, and a public one, which knows which initial values must be passed for those arguments.

For example, in your code, you need to supply the Node root to insertNode. From the perspective of the insertNode recursive process this is crucial. However, from an outside perspective, this makes no sense. If I'm writing the code for the GUI frontend that shows all students, why do I need to supply the node? Your object surely is of type StudentTree or whatnot, it knows the root node, no doubt. (It should, e.g. by being a field, if it doesn't right now).

When you already have the double-method setup, you can also change the return type if you want.

To be clear, this is not feasible without making 2 methods. At best you can return, instead of Node, some combo object that returns the node as well as a boolean and then all callers can unpack it, but this requires a ton of effort (make a class to represent this, and every time you call insertNode, including in insertNode itself, unpack the Node object out).