Tree Traversal (In-order)
Medium+80 XPIn-order traversal of a BST (left → node → right) visits values in sorted order.
No visualization loaded.
Watch
—
Press Run to begin.
A tree is data that branches, like a family tree: one node at the top (the root), each node holding a value and linking down to child nodes. A Binary Search Tree (BST) keeps an order rule: smaller values go left, bigger values go right. 'In-order traversal' visits left child, then the node, then the right child — and because of that rule, it magically spits the values out in sorted order.
▸What are root, node, child, and leaf?
A node is one item in the tree (a value plus links to its children). The root is the single node at the very top — your way in. A child is a node hanging directly below another. A leaf is a node with no children (the tips of the branches). Same 'node + pointers' idea as a linked list, but each node can point to two children instead of one next.
▸What makes it a 'Binary SEARCH Tree'?
Binary = each node has at most two children. Search = the ordering rule: everything in a node's LEFT branch is smaller than it, everything in its RIGHT branch is bigger. That rule lets you find a value by going left/right at each step — like binary search, but on a tree instead of a sorted array.
▸Why does left → node → right give SORTED output?
Because the rule says the left branch is all smaller and the right branch is all bigger. So if you fully handle everything smaller first, then the node, then everything bigger, values come out low-to-high automatically. Watch the animation: the visit order climbs steadily upward.
▸What's this got to do with recursion?
Visiting a node means: traverse its left subtree, visit the node, traverse its right subtree — and 'traverse a subtree' is the same task on a smaller tree. That's recursion (from the factorial lesson) applied to a branching structure, and it's why trees and recursion are taught together.
How the work grows
O(n) — visits every node is fair — grows in step with the data. In-order traversal touches each of the n nodes exactly once, so time grows in a straight line with the tree's size. Space is the depth of the recursion the call stack holds while descending.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.