Top 6 Recursion Interview Questions
Browse 6 real-world technical and behavioral interview questions about Recursion. Review scenarios, edge cases, and architectural best practices.
A bundle can contain products or other bundles, and the pricing code should not care which it is holding. How would you model that?
A composite gives leaves and containers one interface so callers recurse without branching. The two decisions that matter are whether child management appears on that shared interface, and which operations genuinely aggregate - because price, availability and delivery date do not combine the same way. It also connects tree structures to the point an interviewer is testing.
Count the ways to place N queens on an N by N board so that no two attack each other.
One queen per row is forced, so search row by row and keep sets of used columns, used sums and used differences to reject a conflict before recursing. The anti-diagonal is the row plus column and the main diagonal the row minus column, and that difference must be shifted into range, not reduced with an absolute value.
Find the lowest common ancestor of two nodes in a binary tree.
Recurse post-order and return the node whose left and right subtrees each report back one target; if only one side reports back, propagate that result upwards. This is O(n) time and O(h) stack. A BST lets you descend by value comparison instead, and parent pointers reduce it to list intersection. It also connects recursion to the point an interviewer is testing.
Generate every permutation of an array that may contain duplicates, then tell me how large the search tree is
Backtracking builds each candidate incrementally and undoes the last choice on return; duplicates are suppressed by sorting and skipping a repeated value whose identical predecessor is unused. The tree holds under e times n factorial nodes, so pruning only pays when it removes subtrees near the root. It also connects recursion to the point an interviewer is testing.
Serialise a binary tree to a string and reconstruct exactly the same tree from it. What has to be in the string?
A bare traversal is not enough, because two different trees can produce identical node sequences. Emitting an explicit marker for every absent child makes a preorder walk unambiguous, and reading it back is the same walk consuming tokens in the same order from a single cursor.
Given a binary tree, decide whether it is a valid binary search tree.
Every node must fall inside an open interval inherited from its ancestors, not merely compare correctly against its own two children. Recurse carrying a low and high bound, tightening one of them at each descent, or walk in-order and require the sequence to be strictly increasing.