# Leetcode 386 - Lexicographical Numbers

`Note:`

- This is essentially
`pre-order`

traveral of a`10-ary`

tree. `Iterative`

- A single var
`num`

can store our paths. - Keep
`multiplying num`

by`10`

, and add every num to`ans[]`

till it’s bigger or equal to`n`

. - While it’s
`>= n`

or`num % 10 === 9`

, divide num by`10`

.- Question: why do we need to check if
`num % 10 === 9`

? Coz when`num === 19`

, next num should be`2`

instead of`20`

. We need to go all the way back to`top`

level.

- Question: why do we need to check if
- Otherwise do
`num++`

.

- A single var
`Recursion`

- Just like what we’d do in a bianry tree, add
`num`

to`ans[]`

first. - Then do
`DFS`

on every child.`(num * 10 + i)`

- Just like what we’d do in a bianry tree, add

`Question:`

Given an integer `n`

, return all the numbers in the range `[1, n]`

sorted in lexicographical order.

You must write an algorithm that runs in `O(n)`

time and uses `O(1)`

extra space.

`Example:`

1 | Input: n = 13 |

`Code:`

1 | /** |

1 | /** |