InorderTraversal

In this medium-level challenge, you'll implement the type version of binary tree inorder traversal, producing a tuple of values by visiting the left subtree, then the current node, then the right subtree.

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]

/* _____________ Your Code Here _____________ */

interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}
type InorderTraversal<T extends TreeNode | null> = any

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

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

const tree2 = {
  val: 1,
  left: null,
  right: null,
} as const

const tree3 = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null,

Detailed Explanation

We need a tree node interface and a recursive type that traverses in order: left, root, right.

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']>]
  : []

How it works:

• TreeNode defines the shape of a binary tree node with a val, left child, and right child
• [T] extends [TreeNode] checks whether the current node is a real tree node (not null), wrapping in a tuple to avoid distributive conditional types
• If it is a tree node, we recursively traverse the left subtree, include the current node's value, then recursively traverse the right subtree
• If T is null, we return an empty tuple [] as the base case

This challenge helps you understand recursive conditional types over tree structures and how to apply this concept in real-world scenarios.