Height of binary tree type instantiation is excessive

November 11, 2022

I’m playing around in the type system and I’m currently trying to make a reverse level-order traversal at the type level. These are the types I’m working with:

type LEFT = 0;
type VALUE = 1;
type RIGHT = 2;

type List = ReadonlyArray<unknown>;

type Increment<N extends List> = [...N, unknown];
type Decrement<N extends List> = N extends readonly [...infer H, any] ? H : never;

// `Node` already exists as a built-in... so I used Deno...
type Deno = [LEFT: Deno | undefined, VALUE: number, RIGHT: Deno | undefined];

I’m using a tuple instead of an object type to represent nodes since it’ll be easier to create and change testing values. I also have some aliases to make it more "readable" when accessing the data (MyDeno[LEFT] is easier to understand than MyDeno[0]). Also, I’m using tuples to represent numbers, since they’re much easier to work with and don’t need a limit to be manually specified.

I can get the height of a tree in JavaScript like this:

function height(node) {
  if (!node) return 0;

  const lhs = height(node.left);
  const rhs = height(node.right);

  return Math.max(lhs, rhs) + 1;
}

But my attempt at transferring this to the type system generates an error:

type Max<A extends List, B extends List> = A extends [...B, ...any[]] ? A : B;

type Height<Root extends Deno | undefined> =
    Root extends Deno
        ? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>
//            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Type instantiation is excessively deep and possibly infinite.
        : [];

even though it works with sample data:

type Data = [
    [
        [undefined, 4, undefined],
        2,
        [undefined, 5, undefined],
    ],
    1,
    [undefined, 3, undefined],
];

// Should be 3 since the height of `Data` is 3
type T = Height<Data>["length"];
//   ^? 3

I wasn’t expecting this to throw "Type instantiation is excessively deep"… Where in my type is the fault, and how could I refactor my Height type so that it doesn’t throw this error? Until I can correct this, I’ll stick with using //@ts-ignore.

Playground

>Solution :

I’ve noticed that sometimes when recursive conditional types are distributive there is a greater chance of hitting instantiation depth limits than there is when the type is non-distributive.

Thus, one approach I take is to see if I can proceed by turning off distributivity over unions (via the standard one-tuple-wrapper technique X extends Y ? A : B ➝ [X] extends [Y] ? A : B):

type Height<Root extends Deno | undefined> =
    [Root] extends [Deno]
    ? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>  // okay
    : [];

That works, at least for your example code.

Playground link to code