Binary Search Tree Visualization
A Binary Search Tree (BST) is like a well-organized library where each book (node) has a clear place based on its value. In a BST, each node has up to two children: the left child holds smaller values, and the right child holds larger values. This structure allows for efficient searching, adding, and removing of nodes, as you can quickly navigate left or right by comparing values.
Insertion walks down the tree by repeatedly choosing left or right based on comparison, stopping only when it finds an empty spot. The new node is attached as a leaf.
Deletion first locates the target node, then carefully reconnects its children so the BST rule still holds. If the node has no children, it is simply removed. If it has one child, that child takes its place. If the node has two children, the tree replaces it with a nearby node that preserves ordering. Learn the full strategy in our BST deletion guide.
Pseudocode
function insert(node, key):
if key < node.value
if node.left is null:
node.left = new Node(key)
else:
insert(node.left, key)
else if key > node.value:
if node.right is null:
node.right = new Node(key)
else:
insert(node.right, key)
AI Summary
(2 credits)
Common Interview Questions
What is the worst-case time complexity for search, insertion, and deletion in a standard BST?
Worst case is O(n), occurring when elements are inserted in sorted or reverse-sorted order, causing the tree to degenerate into a linear linked list (skewed tree). Average case for balanced BST is O(log n).
Describe the three cases encountered when deleting a node from a BST.
1) Leaf node: Remove directly. 2) One child: Replace node with its child. 3) Two children: Replace node value with its In-Order Successor (smallest value in right subtree), then recursively delete that successor node.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0