InOrderTraversal in TypeScript

stratis 0
Viewed 17

Can anybody explain to me what this error means?

I'm not looking for a solution but rather an understanding of the actual problem here.

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

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

type InOrderTraversal<
  T extends TreeNode | null
> = T extends null
  ? []
  : [
      ...InOrderTraversal<T["left"]>,  // --> Type '"left"' can't be used to index type 'T', 
      T["val"],                        // --> Type '"val"' can't be used to index type 'T',
      ...InOrderTraversal<T["right"]>. // --> Type '"right"' can't be used to index type 'T'
    ];

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

TypeScript playground

Thanks!

inorder tree-traversal typescript
1 Answers

The issue here is probably the way type information is passed down in a conditional type. TypeScript knows that T has to be null in the true branch but inconveniently does not realize that the opposite must be the case in the false branch.

You said that you are not looking for a solution, but here is one anyway :)

type InOrderTraversal<
  T extends TreeNode | null
> = T extends TreeNode
  ? [
      ...(InOrderTraversal<T["left"]> extends infer U extends any[] ? U : never),
      T["val"],
      ...(InOrderTraversal<T["right"]> extends infer U extends any[] ? U : never)
    ]
  : []

I just switched around the conditional so that T is checked to extend TreeNode. Also note that this infer U stuff is needed to supress the type instantiation is excessively deep and possibly infinite errors.

Playground

Tobias S.0
Related