Tree Traversals and Binary Search Trees
The four ways to walk a binary tree, how a binary search tree keeps data ordered, and why an unbalanced one turns into a linked list. Runnable code with real output.
A binary tree can be walked in four standard orders: inorder, preorder, postorder and level order. A binary search tree keeps smaller values in the left subtree and larger values in the right, so an inorder walk returns sorted output. Interviewers expect search and insert to cost O(h), where h is the height, which is n for a degenerate tree.
A binary tree can be walked in four standard orders: inorder, preorder, postorder and level order. A binary search tree (BST) keeps smaller values on the left and larger on the right, so an inorder walk gives sorted output and lookups take O(h), where h is the tree height.
- Inorder traversal visits left, node, right, and on a binary search tree it returns the values in sorted order.
- Preorder (node, left, right) is used to copy or serialise a tree, and postorder (left, right, node) to delete it or compute values bottom-up.
- All four binary tree traversals are O(n) time; depth-first versions use O(h) stack space and level order uses O(w) for the widest level.
- Binary search tree search and insert cost O(h); inserting 1 to 7 in sorted order gives a height of 7, so every search becomes O(n).
- Deleting a BST node with two children copies in its inorder successor, the smallest value in the right subtree, and then deletes that successor.
- A valid BST needs every value in the left subtree to be smaller than the node, not just the immediate child, so validation passes down bounds.
01What a binary tree is
A tree is a set of nodes connected so there is exactly one path between any two. The top node is the root. A node with no children is a leaf. In a binary tree each node has at most two children.
The height is the number of nodes on the longest path from the root to a leaf (some books count edges instead, so ask which one the interviewer means). Almost every cost in this topic is expressed in terms of height, because you never need to go deeper than that.
The tree used in the examples below is built by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 into a BST in that order. 8 is the root, 3 and 10 are its children, 1 and 6 hang under 3, 14 is under 10, and so on.
02Depth-first: inorder, preorder, postorder
class N:
def __init__(self, v):
self.v, self.l, self.r = v, None, None
def insert(root, v):
if root is None:
return N(v)
if v < root.v:
root.l = insert(root.l, v)
else:
root.r = insert(root.r, v)
return root
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
root = insert(root, v)
def inorder(n): return inorder(n.l) + [n.v] + inorder(n.r) if n else []
def preorder(n): return [n.v] + preorder(n.l) + preorder(n.r) if n else []
def postorder(n): return postorder(n.l) + postorder(n.r) + [n.v] if n else []
print(inorder(root)) # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(preorder(root)) # [8, 3, 1, 6, 4, 7, 10, 14, 13]
print(postorder(root)) # [1, 4, 7, 6, 3, 13, 14, 10, 8]Inorder is left, node, right. On a BST it prints the values in sorted order, which is the most useful property to remember. Preorder is node, left, right. It is how you copy or serialise a tree, because the parent comes before its children. Postorder is left, right, node. Children come first, which is what you need to delete a tree or compute something from the bottom up, like the size of every subtree.
03Breadth-first: level order
from collections import deque
def level_order(root):
if root is None:
return []
out, q = [], deque([root])
while q:
n = q.popleft()
out.append(n.v)
if n.l: q.append(n.l)
if n.r: q.append(n.r)
return out
print(level_order(root)) # [8, 3, 10, 1, 6, 14, 4, 7, 13]The depth-first versions use recursion (or an explicit stack). Level order uses a queue. If you need the answer grouped by level, for example "return each level as its own list", process the queue one level at a time by taking its current length first.
All four traversals visit each node once, so they are O(n) time. Space is O(h) for the recursion stack in the depth-first versions, and O(w) in level order, where w is the widest level.
04Searching and inserting in a BST
The BST rule: every value in a node's left subtree is smaller, and every value in the right subtree is larger. To find 7 in our tree, start at 8, go left (7 < 8) to 3, go right (7 > 3) to 6, go right again to 7. Four nodes were touched out of nine.
Insert follows the same path until it falls off the tree and places the new node there, which is what insert above does. Search and insert are both O(h).
A common mistake is to check only that a node is larger than its left child and smaller than its right child. A valid BST needs every node in the left subtree to be smaller than the root, not just the immediate child. To validate a BST, pass down a lower and an upper bound, or check that an inorder walk is strictly increasing.
05Deleting a node
def delete(root, v):
if root is None:
return None
if v < root.v:
root.l = delete(root.l, v)
elif v > root.v:
root.r = delete(root.r, v)
else:
if root.l is None:
return root.r
if root.r is None:
return root.l
s = root.r # inorder successor:
while s.l: # smallest value in the right subtree
s = s.l
root.v = s.v
root.r = delete(root.r, s.v)
return root
root = delete(root, 3)
print(inorder(root)) # [1, 4, 6, 7, 8, 10, 13, 14]
print(root.l.v) # 4Node 3 had two children (1 and 6). Its inorder successor is 4, the smallest value in the right subtree. Copying 4 into the node and then deleting the original 4 keeps the ordering intact. That is why root.l.v is now 4. A leaf is simply removed, and a node with one child is replaced by that child.
06Why balance matters
The costs above are O(h), and h depends on the insertion order. Our nine values gave a height of 4. Insert 1, 2, 3, 4, 5, 6, 7 in that order and every node goes to the right of the previous one. The height is 7 and every search is O(n), no better than scanning an array.
Balanced trees fix this by rotating nodes after inserts and deletes to keep the height near log n. AVL trees and red-black trees are the two you will be asked about. Java's TreeMap and C++'s std::map are red-black trees. Databases use B-trees, which are the same idea with many children per node so each node fills a disk page.
For an interview, you rarely need to code a rotation. You do need to say clearly that a plain BST is O(h), that h can be n, and that balanced trees guarantee O(log n).
07Common interview questions
Q: Which traversal gives sorted output on a BST?
A: Inorder.
Q: How do you find the height of a tree?
A: Recursively: 0 for an empty tree, otherwise 1 plus the larger of the two child heights.
Q: Find the lowest common ancestor in a BST.
A: Start at the root. If both values are smaller, go left. If both are larger, go right. The first node where they split, or equal one of them, is the answer. O(h).
Q: Rebuild a tree from two traversals?
A: Preorder plus inorder, or postorder plus inorder, are enough if values are unique. Preorder alone is not, but it is for a BST because the ordering rule fixes the shape.
Q: BST versus hash table?
A: A hash table is faster for exact lookups (O(1) average). A BST keeps order, so it handles range queries, minimum, maximum, successor and sorted iteration in O(log n) when balanced.