Binary Search Tree (BST)

About

A Binary Tree in which:

• The left child contains values smaller than the parent.

• The right child contains values greater than the parent.

Searching an element

Runs on $O(log N )$ up to $O(N)$ in the worst case, depending on how the Tree structure is.

function findBST(node: BinaryNode<T>, needle: T): boolean {
    if (!node) return false;
    if (node.value === needle) return true;
    if (node.value < needle) return findBST(node.right, needle);
    return findBST(node.left, needle);
}

Inserting an element

Just look for the place that satisfy BST conditions and add.

Will eventually unbalance the tree.

function insertInBST(node: BinaryNode<T>, ancestor: BinaryNode<T>, path: "left" | "right", value: T): void {
    if (!node) {
        const newNode = {
            value,
            left: undefined,
            right: undefined
        }
        ancestor[path] = newNode;
    }
    if (node.value < value) findBST(node.right, node, "right", value);
    else findBST(node.left, node, "left", value);
}

Deleting an element

Deleting is bit more complicated and have 3 separate cases to look for:

• Case 1: The deleted node $X$ has no children, so $Ancestor_X$ just points to undefined.

• Case 2: The deleted node $X$ has only 1 child, so $Ancestor_X$ points to $X$ child.

• Case 3: The deleted node $X$ has both children, so $Ancestor_X$ will point to either:

  • The largest decendent node of $X_{left\ child}$. (largest on small side)

  • The smallest decendent node of $X_{right\ child}$. (smallest on large side)

Having a height property on each node, helps choosing in Case 3 which child has the highest height.

And choosing the child with the highest helps pruning the tree and reducing its height.

function deleteInBST(node: BinaryNode<T>, value: T, ancestor: BinaryNode<T>, path: "left" | "right", value: T): T | undefined {
    
}