Interview Cake
Sometimes we have a BST and we want to go through the items in order from smallest to largest. This is called an "in-order traversal."
We can write a recursive algorithm for this:
- Everything in the left subtree is smaller, so print that first, then,
- print the current node, then
- print the right subtree.
This takes time (we're traversing the whole tree, so we're looking at all n items) and space, where h is the height of the tree (this is the max depth of the call stack during our recursion).
If the tree is balanced its height is lg(n), so we have space. If we can't make any assumptions about the "shape" of the tree, in the worst case it's just one continuous line, giving us a height of n, and a space complexity of for our recursive in-order traversal.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
