A binary tree is a hierarchy where each node has at most two children. A Binary Search Tree (BST) adds a rule: everything in the left subtree is smaller than the node, everything in the right subtree is larger. That ordering makes search behave like binary search — O(log n) when the tree is balanced.
Traverse, then compute
Most tree problems are a traversal plus a small computation at each node. The three depth-first orders differ only in when you visit the node: pre-order (node first), in-order (between children), post-order (node last).
In-order traversal and BST search
function inorder(node):
if node == null: return
inorder(node.left)
visit(node.value) // in-order: left, node, right
inorder(node.right)
function search(node, key):
if node == null or node.value == key: return node
if key < node.value: return search(node.left, key)
return search(node.right, key)Search O(h)→h = height
Balanced -> h = log n; skewed -> h = n.
⚡ The edge
- In-order traversal of a BST yields the values in sorted order — a fact that solves many problems instantly (k-th smallest, validate BST).
- Choose the traversal by need: pre-order to copy a tree, in-order for sorted output, post-order to delete or compute heights bottom-up.
Worked example
In-order traversal of this BST (root 5, left 3, right 8) prints what?
- In-order visits left subtree, then the node, then the right subtree.
- Left (3), then root (5), then right (8).
- So it prints 3, 5, 8 — sorted, as expected for a BST.
Answer: 3, 5, 8 (sorted order)
Worked example
Searching for 8 in that BST: what is the path?
- Start at the root, 5. The key 8 is greater than 5, so go right.
- The right child is 8, which matches the key.
- Found in 2 steps — each comparison discards a whole subtree, like binary search.
Answer: 5 -> 8 (O(h) = O(log n) when balanced)
⚠ Watch out
- A skewed BST (inserting sorted data) degrades to a linked list — O(n) operations; balanced trees (AVL, Red-Black) keep O(log n).
- Always handle null children before recursing.
- Recursion depth equals the tree height — deep trees can overflow the stack.