Algorithm logic flaw in AVLTree.insert()

Data Structures
1

Mosh’s implementation of the insert method leaves out one important check - is value already in our tree. Duplicates are not permitted in a binary search tree and both bloat the size of your tree and slow down navigation of it.

One possible implementation of this check is shown below. If the value already exists in the tree, return null. Because we are passing the references to nodes all the way back up the chain to the root, this would wipe out the entire tree. To prevent that, after the recursive call to insert(), simply check if a call down the chain returned null, and if so, don’t change the value of .leftChild or .rightChild.

private AVLNode insert(AVLNode root, int value) {
    if (root == null)
        return new AVLNode(value);

    if (root.value == value)
        return null;

    var newRoot = (value < root.value)
            ? insert(root.leftChild, value)
            : insert(root.rightChild, value);
    if (value < root.value)
        root.leftChild = (newRoot == null) ? root.leftChild : newRoot;
    else
        root.rightChild = (newRoot == null) ? root.rightChild : newRoot;
    setHeight(root);

    return balance(root);
}

@codewithmosh, this would be a great spot to make a quick edit to the video to show the error, show the fix, and talk about the importance of testing your code with relevant edge cases. It would drive home how simple it is to create broken code if you only test “successful” or “expected” scenarios.

2

Why not just return root for that case? I believe it fixes the problem without making the rest of the code have to deal with that null case.