Flattening binary tree to array: Is there a way to find a node's index in the array when traversing depth-first?

Question

I want to flatten a binary tree like

  2
 / \
1   4
   / \
  3   7

to an array like

{2, 1, 4, null, null, 3, 7}

This is pretty common in my understanding, perhaps even canonical.

I know that if I traverse the tree breadth-first (BFS), say, using a queue to tack on nodes to visit as I come across them, then building such an array is automatic—BFS ordering is exactly the ordering of the array.

But I wondered if there was a way to build the array while traversing depth-first (DFS).

I came up with one scheme that didn't quite work:

1. While traversing recursively, keep track of the level you're on (L), as well as the number of times you went right (R).
2. Then the index is given by the formula, (2^L)-1+R.

Unfortunately, this failed because the order in which left and right "turns" are made, matter.

Is there a different state that can be tracked to yield the index efficiently?

Answer 1

If we're using zero-based indexing, then the nodes at depth d (0 for the root, 1 for the root's direct children, etc.) start at index 2^d−1.

Within the "row" of nodes at a given depth, we can think of each "descend into left child" and "descend into right child" step as a bit: left = 0 (first half), right = 1 (second half). For example, if we start at the root node and go left–left–right, then we'll end up at position 001₂ in the row of depth 3, whereas if we start at the root node and go right–right–left, then we'll end up at position 110₂ in that row.

We can then just add the start-index of the row to the position within the row to get the overall index.

Here's some pseudocode:

get_index(path):
    row_start := 0
    position_in_row := 0
    for element in path:
        row_start := 2 * row_start + 1
        position_in_row := 2 * position_in_row
        if element is 'RIGHT':
            position_in_row := position_in_row + 1
    return row_start + position_in_row

If we're using one-based indexing, then change row_start := 0 to row_start := 1 and row_start := 2 * row_start + 1 to row_start := 2 * row_start.