reconstruct binary tree from its pre-order and in-order traversals

tree.jq

def tree($pre; $in):
  def root($pre; $in):
    def branch($pre; $in):
      $in | if has(0) then
        (index($pre[0]) + 1) as $i | {
          l: root($pre[:$i]; .[:$i]),
          r: root($pre[$i:]; .[$i:])
        }
      else
        {l: {}, r: {}}
      end;
    $pre | if sort != ($in | sort) then
      "traversals must have the same elements" | halt_error
    elif has(0) then
      {v: .[0]} + branch(.[1:]; $in[:-1])
    else
      {}
    end;
  $pre | if length != (unique | length) then
    "traversals must contain unique items" | halt_error
  else
    root(.; $in)
  end;

tree(
  ["z","p","i","a","h","f","d","b","c","e","g","o","m","l","j","k","n","y","q","x","t","r","s","w","u","v"];
  ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
)