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.
In-Order Traversal of a Binary Search Tree interview questions to practice
Each one walks you through a real coding interview problem one hint at a time.
- 2nd Largest Item in a Binary Search Tree » Find the second largest element in a binary search tree.
- Binary Search Tree Checker » Check whether a binary tree is a valid binary search tree. Avoid the common gotcha and solve it in O(n) time. A classic interview question, step by step.
Your first 3 questions are free. Just sign in, no credit card.
See also:
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!
