InorderTraversal

Challenge

Implement the type version of binary tree inorder traversal.

For example:

const tree1 = {
  val: 1,
  left: null,
  right: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null,
    },
    right: null,
  },
} as const;

type A = InorderTraversal<typeof tree1>; // [1, 3, 2]

Solution

Zur Lösung dieses Problems sollten wir zuerst eine Bedingung für den Typen definieren. Hier sollten nur TreeNode oder null als Parameter angegeben werden können. Dies kann mittels einer Kondition für Generics erreicht werden:

type InorderTraversal<T extends TreeNode | null>

Nun müssen wir noch rekursiv den Typ für beide Teile des Baumes aufrufen, und das Ergebnis beider Seiten in einer Tupel zusammenführen. Wichtig ist dabei, beide Seiten der extends Bedingung in Klammern zu packen, damit das distributive Verhalten zu verhindern.

type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode]
  ? [...InorderTraversal<T["left"]>, T["val"], ...InorderTraversal<T["right"]>]
  : [];

References

• Variadic tuple types Rest Parameters and Arguments Distributive Conditional Types