Interactive Lab · DSA & Algorithms

Grow a binary search tree, then walk it four ways

A binary search tree keeps one promise at every node: everything in the left subtree is smaller, everything in the right is bigger. That single rule makes search, insert and delete cost one comparison per level, so a bushy tree of a million keys answers in about 20 steps. Insert and delete values below (try deleting a node with two children, the case interviewers love), then run the four traversals and watch the output build up. Two surprises are waiting: in-order comes out sorted, and sorted input wrecks the tree.

▶ The playground, insert, delete, then traverse

current nodesearch pathin-order successorvisited / placed

Type a value and Insert it: it walks down from the root, going left if smaller, right if bigger, until it finds an empty spot. Delete handles three cases: a leaf just vanishes, a node with one child is replaced by that child, and a node with two children borrows its in-order successor (the smallest value in its right subtree). Tap a node to put its value in the box.

value sorted input

traversal

speed 3 / 5

🧭 Where this fits

Binary search trees are the idea under every ordered map: C++ std::map and Java TreeMap are self-balancing BSTs (red-black trees), and database indexes are their wide cousins, B-trees. Traversals are the interview workhorse: in-order to validate a BST or find the k-th smallest, pre-order to serialise and copy a tree, post-order to delete or evaluate an expression tree bottom-up, and level-order (BFS) for “right-side view” and minimum depth.

The code that's actually running, insert, delete and the four walks

🔮 Predict, then test

Tick sorted input and hit random tree. Predict first: inserting 7 values in increasing order into an empty BST, how tall does the tree get? Each new value is bigger than everything already there, so it always goes right, and the tree becomes a linked list of height 7, where a balanced tree would need only 3 levels. Search now costs O(n), not O(log n). Then run in-order on any tree: why does it always print the values sorted?

The takeaway

Your new mental model of binary search trees

One rule, applied at every node. Left subtree < node < right subtree. Search, insert and delete all just follow it downward, so they cost O(height).
In-order of a BST is sorted. Left first (all smaller), then the node, then right (all bigger), recursively. That is why “validate a BST” is just “check in-order is increasing”.
Delete has three cases. Leaf: remove it. One child: splice the child up. Two children: copy in the in-order successor (leftmost node of the right subtree), then delete that successor, which has at most one child.
Height is everything. A random tree stays about O(log n) tall; sorted input makes a degenerate chain of height n. Self-balancing trees (AVL, red-black) rotate to keep height logarithmic.
Four walks, four jobs. Pre-order copies, in-order sorts, post-order cleans up children before parents, level-order goes row by row with a queue.

← Recursion Placement prep →Try: Graph BFS