Nth Node at Level L in a 0/1 Tree
A binary tree of 0s and 1s: the root is 0, each left child equals its parent, and each right child is its parent flipped. Levels are numbered from 1 at the root, and positions within a level from 1 on the left. Given a level l and a position n, return that node's value.
level 1: 0 level 2: 0 1 level 3: 0 1 1 0 level 4: 0 1 1 0 1 0 0 1 kthGrammar(3, 3) -> 1 kthGrammar(4, 5) -> 1
l can be 30, so the level holds half a billion nodes.
Hints
Hint 1
Level l has 2^(l−1) nodes and its left half is level l−1 verbatim; its right half is level l−1 flipped. So if n is in the left half the answer is unchanged, otherwise it is 1 minus the answer for the mirrored position.
Hint 2
Closed form: each right turn on the path from the root flips the value, and the right turns are exactly the set bits of n − 1. The answer is the parity of popcount(n − 1).