Time complexity gets analysed because time limits are the ones people hit. Space limits are usually generous enough that the question never comes up — until a problem is set specifically to make it come up, or an interviewer asks for the space bound and the answer is visibly a guess.
One: recursion depth is space
A recursive solution allocating nothing still costs O(depth) stack space. On a balanced tree that is O(log n) and unremarkable. On a degenerate tree, a linked list, or a path-shaped graph it is O(n) — and it is the reason the same solution both times out and crashes on the same test.
If you claim O(1) space for a recursive function, you are almost certainly wrong. The iterative version of a BST descent genuinely is O(1); the recursive version is O(h).
Two: slicing copies
In Python, Java and most managed languages, a slice allocates. Recursing on slices of a string of length n allocates O(n²) characters in total. Pass indices instead of substrings — it is the same algorithm with the copies removed.
If a recursive signature takes a list or string that shrinks each call, check whether the language copies. Passing (arr, lo, hi) is nearly always the fix.
Three: materialising what you only needed to stream
Kth smallest in a BST is the standard example. Building the whole inorder traversal into a list and indexing it is O(n) space and O(n) time regardless of k. Walking inorder with a counter and stopping early is O(h) space and O(h + k) time.
Four: the DP table you did not need in full
A great many DP recurrences only reference the previous row. Keeping the full table is O(n·m); keeping two rows is O(m); sometimes one row updated in the right direction is enough. The knapsack rolling array is exactly this, and the direction of the inner loop is what makes it correct.
How to audit your own solution
- →Name every allocation that scales with the input.
- →Add the maximum recursion depth.
- →Check whether any slice, split, or copy sits inside a loop or a recursive call.
- →Ask whether any structure is built in full when it could be consumed incrementally.
Four questions, thirty seconds. It is the difference between saying 'O(1) space, I think' and being able to defend the number.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.