03376-medium-inordertraversal

Back 

type InorderTraversal<T extends TreeNode | null, NT extends TreeNode = NonNullable<T>>  =  T extends null ? [] : [...InorderTraversal<NT['left']>,NT['val'],...InorderTraversal<NT['right']>]

Solution by devshinthant #35260 

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

type InorderTraversal<T extends TreeNode | null, NT extends TreeNode = NonNullable<T>> = T extends null
  ? []
  : [...InorderTraversal<NT['left']>, NT['val'], ...InorderTraversal<NT['right']>]

Solution by devshinthant #35027 

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

Solution by Jayce-liang #34778

I see other solutions use [T] extends [TreeNode] to prevent distribution, but that should not be needed:

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

Solution by cipak #34617 

// δΈ­εΊιεŽ†
type InorderTraversal<T extends TreeNode | null> = T  extends TreeNode ? [...InorderTraversal<T['left']>, T['val'], ...InorderTraversal<T['right']>] : []

Solution by ouzexi #34065

type InorderTraversal<T extends {val:any, left:any, right:any}, A extends any[]= []> = T extends { left: infer L, val: infer V, right: infer R }?[...InorderTraversal<L, A>, V, ...InorderTraversal]:A

Solution by rookiewxy #33923 

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

Solution by kai-phan #32518 

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

Solution by Zhen-code #31984 

type InorderTraversal<T extends TreeNode | null, S extends TreeNode = T & TreeNode> = T extends TreeNode
  ? [ ...InorderTraversal<S['left']>, T['val'], ...InorderTraversal<S['right'] ]
  : []

Solution by jbalancer #31607 

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

// According to the below JS code, we can write corresponding ts code easily
const inorderTraversal = (root: TreeNode | null): number[] => {
  return root === null ? [] : [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
}

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

Solution by GodAraden #30788 

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

Solution by 8471919 #30079

Solution:


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

Solution by DmitriiBr #29679 

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

type Tree<T extends number> = {val: T, right: Tree<T>, left: Tree<T>};

type InorderTraversal<T extends Tree<number>> = T extends null ?
    [] : [...InorderTraversal<T['left']>, T['val'], ...InorderTraversal<T['right']>];

type B = InorderTraversal<typeof tree1>;

Solution by sundial-dreams #29497 

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

Solution by DoubleWoodLin #28720 

interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}
type InorderTraversal2<T extends TreeNode | null, R extends number[] = [], FromLeft = false> =
    T extends TreeNode
      ? T['left'] extends null
        ? T['right'] extends TreeNode
          ? InorderTraversal2<T['right'], [...R, T['val']], FromLeft>
          : FromLeft extends true
            ? [...R, T['val']]
            : R
        : InorderTraversal2<T['left'], R, true>
      : T extends null
        ? []
        : never

type FindRightest<T extends TreeNode | null> = T extends TreeNode
  ? T['right'] extends TreeNode
    ? FindRightest<T['right']>
    : [T['val']]
  : []

type InorderTraversal<T extends TreeNode | null> = [...InorderTraversal2<T>, ...FindRightest<T>]

Solution by jazelly #27684 

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

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

Solution by se030 #26947 

// your answers
type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode]
  ? [
      ...InorderTraversal<T['left']>,
      T['val'],
      ...InorderTraversal<T['right']>
    ]
  : []

Solution by CheolMinBae #26887 

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

Solution by jsujeong #26886 

// your answers

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

Solution by hhk9292 #26885 

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

// type InorderTraversal<T extends TreeNode | null>
//   = T extends TreeNode
//     ? [
//         ...(T['left'] extends TreeNode ? InorderTraversal<T['left']> : []),
//         T['val'],
//         ...(T['right'] extends TreeNode ? InorderTraversal<T['right']> : []),
//       ]
//     : []

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

Solution by tokyo9pm #26730

My solution woks but has two error, can anyone figure out how to fix this? image

// your answers
type InorderTraversal<T extends TreeNode | null> =
  T extends {
    val: infer V extends number
    left: infer L extends TreeNode | null
    right: infer R extends TreeNode | null
  }
    ? [...InorderTraversal<L>, V, ...InorderTraversal<R>]
    : []

Solution by adoin #26222 

// your answers
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}
type InorderTraversal<T extends TreeNode | null> = 
  T extends TreeNode
  ? [
      ...(
        T['left'] extends TreeNode
        ? InorderTraversal<T['left']>
        : []
      ),
      T['val'],
      ...(
        T['right'] extends TreeNode
        ? InorderTraversal<T['right']>
        : []
      ),
    ]
  : [];

Solution by kiki-zjq #25163 

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

Solution by yungo1846 #24836

3376 - InorderTraversal

If you're anything like me, when you see something that talks about tree traversal, a little bead of sweat forms on your forehead like happens in anime shows. Don't worry though. Once you take a look at this one it's pretty gentle and the alternatives have something cool to offer.

πŸŽ₯ Video Explanation

Release Date: 2023-03-03 19:00 UTC

InorderTraversal

πŸ”’ Code

// ============= Test Cases =============
import type { Equal, Expect } from './test-utils'

type A1 = InorderTraversal<null>;
type B1 = [];
type C1 = Expect<Equal<A1, B1>>;

const tree1 = {
  val: 1,
  left: null,
  right: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null,
    },
    right: null,
  },
} as const;
type A2 = InorderTraversal<typeof tree1>;
type B2 = [1, 3, 2];
type C2 = Expect<Equal<A2, B2>>;

const tree2 = {
  val: 1,
  left: null,
  right: null,
} as const;
type A3 = InorderTraversal<typeof tree2>;
type B3 = [1];
type C3 = Expect<Equal<A3, B3>>;

const tree3 = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null,
  },
  right: null,
} as const;
type A4 = InorderTraversal<typeof tree3>;
type B4 = [2, 1];
type C4 = Expect<Equal<A4, B4>>;

const tree4 = {
  val: 1,
  left: null,
  right: {
    val: 2,
    left: null,
    right: null,
  },
} as const;
type A5 = InorderTraversal<typeof tree4>;
type B5 = [1, 2];
type C5 = Expect<Equal<A5, B5>>;


// ============= Your Code Here =============
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}
type InorderTraversal<T extends TreeNode | null> =
  T extends TreeNode
  ? [
      ...(
        T['left'] extends TreeNode
        ? InorderTraversal<T['left']>
        : []
      ),
      T['val'],
      ...(
        T['right'] extends TreeNode
        ? InorderTraversal<T['right']>
        : []
      ),
    ]
  : [];

// ============== Alternatives ==============
type InorderTraversal<
  T extends TreeNode | null,
  NT extends TreeNode = NonNullable<T>
> = T extends null
  ? []
  : [
      ...InorderTraversal<NT['left']>,
      NT['val'],
      ...InorderTraversal<NT['right']>
  ];

type Val<
  T extends TreeNode | null,
  U extends TreeNode = NonNullable<T>
> =
  T extends null
  ? []
  : [U['val']];
type Left<
  T extends TreeNode | null,
  U extends TreeNode = NonNullable<T>
> =
  T extends null
  ? []
  : InorderTraversal<U['left']>;
type Right<
  T extends TreeNode | null,
  U extends TreeNode = NonNullable<T>
> =
  T extends null
  ? []
  : InorderTraversal<U['right']>;
type InorderTraversal<
  T extends TreeNode | null
> = [...Left<T>, ...Val<T>, ...Right<T>];


type InorderTraversal<
  T extends TreeNode | null
> =
  // this allows skipping the null check
  // by blocking conditional type distributivity
  [T] extends [TreeNode]
  ? [
      ...InorderTraversal<T['left']>,
      T['val'],
      ...InorderTraversal<T['right']>,
    ]
  : [];

βž• More Solutions

For more video solutions to other challenges: see the umbrella list! https://github.com/type-challenges/type-challenges/issues/21338

Solution by dimitropoulos #24322 

type InorderTraversal<T extends TreeNode | null> = T extends TreeNode ? [
  ...(T[`left`] extends TreeNode ? InorderTraversal<T[`left`]/*only TreeNode*/> : []),
  T[`val`],
  ...(T[`right`] extends TreeNode ? InorderTraversal<T[`right`]/*only TreeNode*/> : [])] :
  []/*pop*/;
// ι˜²ζ­’ζ— ι™ι€’ε½’οΌšεŽŸη†ζ˜―εœ¨extendsε·¦δΎ§ε…ˆθ‡ͺθ‘Œζ–­θ¨€οΌŒζ‰“ζ–­θ”εˆη±»εž‹ηš„θ‡ͺεŠ¨εˆ†ε‘

// other way
// type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode] ? [
//   ...InorderTraversal<T[`left`]>,
//   T[`val`],
//   ...InorderTraversal<T[`right`]>] :
//   []/*pop*/;

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

Solution by E-uler #23939 

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

Solution by snakeUni #22760 

// your answers
type InorderTraversal<
  T extends TreeNode | null, 
  C extends readonly [] = []
> = T extends TreeNode ?
    T['left'] extends TreeNode ? [...InorderTraversal<T['left'], C>, T['val']] :
    T['right'] extends TreeNode ? [T['val'], ...InorderTraversal<T['right'], C>] : [...C, T['val']] 
  : C;

Solution by jxhhdx #22714 

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

Solution by Karamuto #21367 

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

Solution by sanketvgh #21329 

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

Solution by jgjgill #21013