What is the time complexity of this insertion?

The time complexity is $O(h)$ where $h$ is the height of the tree. In the worst case (a degenerate tree), this is $O(n)$. In the average case for a randomly built BST, it is $O(\log n)$.

Does inserting a node change the structure of existing nodes?

No. In a standard BST, the new node is always added as a leaf. No existing links between parent and child nodes are broken or reorganized.

How are duplicates handled?

This depends on the specific implementation requirements. Standard mathematical sets reject duplicates. If duplicates are allowed, they are typically routed strictly to the right child (or strictly to the left) at every equality.

How to insert into a binary search tree

Inserting into a binary search tree (BST) requires traversing from the root to a leaf, comparing the new value against each node to find the correct null pointer. This method applies to standard, unbalanced binary search trees where every left descendant is smaller and every right descendant is greater than the parent node.

The setup

You require a valid binary search tree (which may be empty) and a new value $v$ to insert. Each node in the tree must contain a value, a pointer to a left child, and a pointer to a right child.

The steps

If the tree is empty, create a new node with value $v$ , set it as the root, and stop. 2. Initialize a pointer to the root of the tree. 3. Compare $v$ to the current node's value. 4. If $v$ is less than the current node, check the left child. If it is null, create a new node with $v$ as the left child and stop; otherwise, update the pointer to the left child and return to step 3. 5. If $v$ is greater than the current node, check the right child. If it is null, create a new node with $v$ as the right child and stop; otherwise, update the pointer to the right child and return to step 3.

Checking the result

Perform an in-order traversal of the tree after the insertion. The output must be a strictly increasing sequence of values. If any value is out of order, the BST property has been violated.

Common errors

Failing to handle duplicate values consistently is a frequent error; you must define whether duplicates go to the left, go to the right, or are rejected. Another common mistake is losing the reference to the parent node during pointer updates, resulting in an unlinked tree.

Worked example

Insert the value 4 into a BST where the root is 5, its left child is 2, its right child is 8, the left child of 2 is 1, and the right child of 2 is 3.

Compare the new value 4 to the root value 5. Since 4 < 5, move to the left child, which is 2. Compare 4 to 2. Since 4 > 2, move to the right child, which is 3. Compare 4 to 3. Since 4 > 3, attempt to move to the right child. The right child of 3 is null. Create a new node with value 4 and assign it as the right child of the node containing 3.

FAQ

Run your own problem

Answer form

References: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein · Algorithms by Sedgewick and Wayne