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.

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.