Binary trees and traversal orders
A binary search tree keeps every left subtree below its node and every right subtree above it. That invariant makes search, insertion, and deletion O(log n) on a balanced tree — and O(n) on a degenerate one, which is precisely why balanced variants such as AVL and red-black trees exist.
Traversal order is the other half of tree interviews. In-order visits a BST in sorted order, pre-order copies structure, post-order frees children before parents, and level-order explores breadth-first with a queue.
Time and space complexity
| Operation | Balanced | Worst (skewed) | Space |
|---|---|---|---|
| Search | O(log n) | O(n) | O(h) recursion |
| Insert | O(log n) | O(n) | O(h) recursion |
| Delete | O(log n) | O(n) | O(h) recursion |
| In-order traversal | O(n) | O(n) | O(h) |
| Level-order traversal | O(n) | O(n) | O(w) queue width |
How to use this visualizer
Insert several values and watch the comparison path from the root.
Run each traversal and compare the emitted order.
Confirm that in-order on a BST produces a sorted sequence.
Insert already-sorted values to build a skewed tree and see O(n) appear.
Frequently asked questions
They differ in when the node is visited relative to its subtrees. In-order visits left, node, right — on a BST this yields sorted output. Pre-order visits node, left, right, which is useful for serialising or copying a tree because the root arrives first. Post-order visits left, right, node, which suits deleting or evaluating expression trees since children resolve before their parent.
Comparing each node against only its immediate children is the classic wrong answer — it accepts trees that violate the invariant deeper down. Instead recurse carrying a permitted (min, max) range: the left child inherits (min, node.value) and the right child inherits (node.value, max). Any node outside its range invalidates the tree. O(n) time, O(h) space.
A BST's operations cost O(h), where h is the height. A balanced tree keeps h at Θ(log n), but inserting sorted data into a plain BST produces a linked list with h = n, degrading every operation to O(n). AVL and red-black trees restore balance through rotations on insert and delete, guaranteeing logarithmic height.