Trees

Binary search tree insert, search, and delete walkthroughs

Trees: Binary Search Tree

Tree

BST State

Operation

idle

Current Node

—

Visited Path

Select an operation to trace the path.

Result

Idle

Tree Height

Node Count

→ Binary search trees keep smaller values on the left and larger values on the right.

Insert walks down the tree until it finds the first empty child slot, then adds the new value there.

Search follows comparisons from the root and stops when the target is found or a null branch is reached.

Delete removes the node and, when needed, promotes the in-order successor to preserve BST ordering.

Insert

Time:O(h)

Space:O(1)

Time:O(h)

Space:O(1)

Delete

Time:O(h)

Space:O(1)