Predict the output
What does this print?
import sys
print(sys.getrecursionlimit())Choose an answer, then open Show answer below to check it.
Answer: A 1000
Right: CPython's default recursion limit is 1000.
A chain-shaped tree deeper than the limit makes recursive walks fail, which is when an explicit stack helps.
Recursion uses one stack frame per level, so its depth equals the tree's height. On balanced trees that is about log₂ n, tiny even for millions of nodes. On a chain-shaped tree it is n, and CPython stops at about 1000 frames by default. Use an explicit stack (DFS) or queue (BFS) when the height can be large.
Explain when to avoid recursion on trees.
Say your answer out loud, then check which of these points you covered:
Interviewers usually accept recursion; mention the depth limit and offer the iterative version.
Iterative in-order needs the 'go left, pop, go right' loop; pre-order is the easiest to convert.
Kotlin on the JVM has a deeper default stack, but very deep recursion still overflows.
Ask whether the tree can be very deep. It shows you think about inputs, not just the happy path.
Think of your answer first, then open the hint.
How deep can a search tree get?
As deep as the number of keys if inserted in sorted order.
Does tail-call optimisation help?
Python and the JVM do not do it automatically; Kotlin's tailrec only works for self-calls in tail position.
What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal
From the author
Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.
Suggest a fix if something here is wrong or out of date.