Lexicographical Numbers: DFS Without a Tree

Lexicographical Numbers is LeetCode 386, rated Medium. Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order. The catch: you must do it in O(n) time and O(1) extra space (not counting the output list).

Example: given n = 13, the output is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]. Notice how 10 through 13 come right after 1, because "10" comes before "2" when you sort strings alphabetically.

Sorting the numbers as strings would take O(n log n), which is too slow. The question is really asking: can you generate them in lexicographic order directly, without sorting?

The key insight

The numbers 1 through n form a virtual 10-ary trie. The root has children 1 through 9. Each node with value v has children v*10 through v*10 + 9, as long as those children do not exceed n. A preorder DFS of this trie produces exactly the lexicographic ordering.

You never build the trie. You just walk it. At each step you decide: should I go deeper (multiply by 10) or move to the next sibling (add 1)? When a sibling overflows its parent's subtree, you backtrack by dividing by 10.

The approach

1. Start with current = 1.
2. Add current to the result.
3. Try to go deeper: if current * 10 is within n, set current = current * 10 (this is like visiting the first child in DFS).
4. Otherwise, try to move to the next sibling: increment current by 1. But if current now ends in 0 or exceeds n, that means you have left the current subtree. Divide by 10 to backtrack to the parent, then increment.
5. Repeat until you have collected all n numbers.

The backtracking logic handles the transition from, say, 13 back up to 2. After processing 13, the next sibling would be 14, which exceeds n = 13. So you divide by 10 to get 1, then add 1 to get 2. That is the DFS unwinding back to the root and moving to the next branch.

The code

def lexical_order(n):
    result = []
    current = 1
    for _ in range(n):
        result.append(current)
        if current * 10 <= n:
            current *= 10
        else:
            while current == n or current % 10 == 9:
                current //= 10
            current += 1
    return result

The inner while loop handles two situations. First, when current == n, you cannot increment further at this depth, so you backtrack. Second, when current ends in 9, incrementing it would roll the last digit from 9 to 0, which means you have exhausted all siblings at this level and need to go back up. Both cases require dividing by 10 and then incrementing at the parent level.

Complexity

Time: O(n). The outer loop runs exactly n times, once per number. The inner while loop backtracks up levels of the trie, but each backtrack step corresponds to a descent that already happened. Over the entire run, the total number of descent and backtrack operations is bounded by O(n), because each of the n numbers is visited once.

Space: O(1). Beyond the output list, only a single integer (current) is used. No recursion stack, no explicit trie, no additional data structures. If you count the output list, space is O(n), but the problem requires returning it so that does not count as extra.

Building blocks

Virtual tree DFS

The core pattern here is treating a numeric range as a tree and traversing it without materializing the tree. You define the parent-child relationship implicitly (multiply by 10 to go deeper, divide by 10 to go up, add 1 to visit a sibling) and walk the structure with a single pointer.

This "virtual tree" thinking appears in other problems too. Anytime a problem has a natural tree structure but does not give you an actual tree data structure, you can often walk it with the same go-deeper-or-backtrack logic. Problems involving nested directory paths, decimal expansions, or hierarchical numbering systems all share this flavor.

Preorder traversal without recursion

The solution is an iterative preorder traversal. You process the current node first (append to result), then try the first child, then siblings, then backtrack. This is the same order as a recursive DFS that processes before recursing, but done with a while loop and arithmetic instead of a call stack. The same iterative preorder pattern shows up in Binary Tree Preorder Traversal, but there you have explicit left/right pointers. Here you have implicit 10-way branching.

Edge cases

• n = 1. The output is just [1]. The loop runs once, appends 1, and since 10 > 1, it tries to increment. current == n triggers the backtrack, dividing by 10 to get 0, then incrementing to 1. But the loop has already finished, so nothing goes wrong. Make sure your solution handles this single-element case.
• n = 9. All single-digit numbers. No child is ever reachable (10 > 9, 20 > 9, etc.), so the traversal just increments 1 through 9 linearly.
• n is a power of 10 (like 100). The trie becomes very deep along the path 1 -> 10 -> 100. The traversal dives all the way down before visiting siblings. Verify that the backtracking from 100 correctly returns to 11 (not to 2).
• Large n (up to 50000). The trie is four levels deep at most. The algorithm handles this fine since it is O(n) regardless of depth.

From understanding to recall

The trick to this problem is seeing the trie that is not there. Once you see it, the solution is just iterative preorder DFS with arithmetic for navigation. But the details of the backtracking loop are easy to get wrong, especially the two conditions (current == n and current % 10 == 9). Those are the lines you need to have memorized cold.

Spaced repetition helps you lock in those conditions. You write the solution from scratch after a day, then three days, then a week. Each time, you reconstruct the while loop and verify: why divide when current equals n? Why divide when the last digit is 9? After a few reps, the logic stops feeling like something you derived and starts feeling like something you just know.

Related posts

• Implement Trie - Build the trie data structure that this problem walks virtually
• Binary Tree Preorder Traversal - The same DFS order but on an explicit binary tree, with both recursive and iterative approaches
• Verify Preorder Serialization of a Binary Tree - Another problem where understanding DFS traversal order is the key insight