Building binary trees from inorder-depth lists - Eli Bendersky's website

An In-Order Depth Representation for Rebuilding Trees

While working on an Advent of Code problem, I came across an interesting tree representation. A binary tree representing nested pairs—where each pair contains either a number or another pair—can be fully described by a list of its leaf values together with their depths in the tree. This works because the tree structure is constrained: every internal node has exactly two children, and leaves hold numbers.

For the nested pair ((6 9) ((3 4) 2)), the tree looks like this:

The numbered lines in the diagram indicate depth: the root is at depth 0, its children at depth 1, and so on. The in-order depth representation of this tree is a sequence of (value, depth) pairs:

(6 2) (9 2) (3 3) (4 3) (2 2)

This is just a list of leaf values—no internal nodes are stored. Normally, you can't rebuild a tree from its in-order traversal alone, but with the added depth markers (and the tree's structural constraints), reconstruction is possible.

Below are two reconstruction algorithms. The first is recursive, compact, and somewhat difficult to follow. The second is iterative and easier to reason about step by step.

The Data Structures

The input is a slice of items, each with a numeric value and a depth:

type DItem struct {
  Value int
  Depth int
}

type DList []DItem

The tree itself is a standard binary tree with numeric leaves:

type Tree struct {
  Value       int
  Left, Right *Tree
}

A Recursive Approach

Here is the recursive reconstruction:

func (dl DList) BuildTreeRec() *Tree {
  cursor := 0

  var builder func(depth int) *Tree
  builder = func(depth int) *Tree {
    if cursor >= len(dl) {
      return nil
    }

    var left *Tree
    if dl[cursor].Depth == depth {
      left = &Tree{Value: dl[cursor].Value}
      cursor++
    } else {
      left = builder(depth + 1)
    }

    var right *Tree
    if dl[cursor].Depth == depth {
      right = &Tree{Value: dl[cursor].Value}
      cursor++
    } else {
      right = builder(depth + 1)
    }
    return &Tree{Left: left, Right: right}
  }

  return builder(1)
}

This relies on double recursion and a mutable cursor that points to the next item to process—effectively popping from the front of the list. The recursion depth matches the tree depth: when the next item's depth equals the current level, we build a leaf; otherwise, we recurse deeper to create an internal node. The key invariant: the rest of the list describes a subtree, and the builder handles each side in turn.

While correct, this style can be hard to hold in your head. An iterative version makes the mechanics more visible.

An Iterative Construction

Let's rebuild the sample tree step by step, starting with the root already in place. The steps below correspond to inserting the first six nodes, and the figure follows along:

1. For (6 2), we need to descend to depth 2. The root's children live at depth 1, so we create the left internal child and move to it.
2. From there, depth 2 children are available—insert 6 as a left child.
3. For (9 2): the node we just inserted is a leaf, so backtrack to its parent. Insert 9 as the parent's right child.
4. For (3 3): both children of the parent are now filled, so we ascend—first to that parent, then to the root. The root has a left but no right child, so create it.
5. The new right child is an internal node at depth 1. Since depth 2 doesn't match 3, create its left child and move there.
6. Now at depth 2, this node's children are depth 3—insert 3 as a left child.

The traversal follows strict in-order: go left as deep as the depths require, then backtrack and move right when the data dictates.

To implement this, you need a way to reach a parent. You could store parent pointers in each node, but here we use an explicit stack of parent nodes—cleaner and easy to rewrite with links if you prefer:

// BuildTree builds a Tree from a DList using an iterative algorithm.
func (dl DList) BuildTree() *Tree {
  if len(dl) == 0 {
    return nil
  }
  // result is the tree this function is building. The result pointer always
  // points at the root, so we can return it to the caller. t points to the
  // current node being constructed throughout the algorithm.
  result := &Tree{}
  t := result

  // depth is the current depth of t's children.
  depth := 1

  // stack of parent nodes to implement backtracking up the tree once we're done
  // with a subtree.
  var stack []*Tree

  // The outer loop iterates over all the items in a DList, inserting each one
  // into the tree. Loop invariant: all items preceding this item in dl have
  // already been inserted into the tree, and t points to the node where the
  // last insertion was made.
nextItem:
  for _, item := range dl {
    // The inner loop find the right place for item in the tree and performs
    // insertion.
    // Loop invariant: t points at the node where we're trying to insert, depth
    // is the depth of its children and stack holds a stack of t's parents.
    for {
      // Check if item can be inserted as a child of t; this can be done only if
      // our depth matches the item's and t doesn't have both its children yet.
      // Otherwise, t is not the right place and we have to keep looking.
      if item.Depth == depth && t.Left == nil {
        t.Left = &Tree{Value: item.Value}
        continue nextItem
      } else if item.Depth == depth && t.Right == nil {
        t.Right = &Tree{Value: item.Value}
        continue nextItem
      }

      // We can't insert at t.
      // * If t does not have a left child yet, create it and repeat loop with
      //   this left child as t.
      // * If t does not have a right child yet, create it and repeat loop with
      //   this right child as t.
      // * If t has both children, we have to backtrack up the tree to t's
      //   parent.
      if t.Left == nil {
        stack = append(stack, t)
        t.Left = &Tree{}
        t = t.Left
        depth++
      } else if t.Right == nil {
        stack = append(stack, t)
        t.Right = &Tree{}
        t = t.Right
        depth++
      } else {
        // Pop from the stack to make t point to its parent
        t, stack = stack[len(stack)-1], stack[:len(stack)-1]
        depth--
      }
    }
  }

  return result
}

The iterative version uses a loop where recursion's call stack is replaced by the parent stack. Once you see that, what the recursive version is doing also becomes clearer—both algorithms are structurally identical.

A note of gratitude: this iterative formulation came from a discussion with my wife, and the initial inspiration was from Tim Visée's Rust approach.