# L12: Recursion II: Chains and Trees

## Starter Types

Use these types and sample values for the exercises:

```ts
type ListNode = { value: string; next?: ListNode };

const c: ListNode = { value: "hit" };
const b: ListNode = { value: "miss", next: c };
const a: ListNode = { value: "hit", next: b };

type TreeNode = { value: number; left?: TreeNode; right?: TreeNode };

const sampleTree: TreeNode = {
  value: 4,
  left: {
    value: 3,
    left: { value: 2 },
  },
  right: { value: 8 },
};
```

## Programming Challenge

Complete the helper groups below. Predict the expected outputs before running checks.

## Exercise 1: Review Chain Recursion

Complete the helpers. For each one, write the base case before the recursive case.

```ts
function countNodes(node: ListNode | undefined): number {
  // TODO: empty chain

  // TODO: current node plus the smaller chain
}

function contains(node: ListNode | undefined, target: string): boolean {
  // TODO: empty chain

  // TODO: match at this node

  // TODO: search the smaller chain
}

function countMatches(node: ListNode | undefined, target: string): number {
  // TODO: empty chain

  const here = node.value === target ? 1 : 0;

  // TODO: combine here with the smaller answer
}
```

Expected checks:

```ts
countNodes(undefined) === 0;
countNodes(c) === 1;
countNodes(a) === 3;

contains(a, "hit") === true;
contains(a, "miss") === true;
contains(a, "coin") === false;

countMatches(a, "hit") === 2;
countMatches(a, "coin") === 0;
```

## Exercise 2: Factorial With Invalid Input

Complete `factorial`. The function should return `undefined` for negative input.

```ts
function factorial(num: number): number | undefined {
  // TODO: invalid input

  // TODO: base case for 0!

  const next = factorial(num - 1);

  // TODO: handle undefined before multiplying

  // TODO: combine num with the smaller answer
}
```

Expected checks:

```ts
factorial(-1) === undefined;
factorial(0) === 1;
factorial(4) === 24;
```

## Exercise 3: Tree Count And Sum

Each missing child is a base case with value `0`.

```ts
function countTreeNodes(root: TreeNode | undefined): number {
  // TODO: missing tree

  // TODO: current node plus left branch plus right branch
}

function sumTreeNodes(root: TreeNode | undefined): number {
  // TODO: missing tree

  // TODO: current value plus left sum plus right sum
}
```

Expected checks:

```ts
countTreeNodes(undefined) === 0;
countTreeNodes(sampleTree) === 4;

sumTreeNodes(undefined) === 0;
sumTreeNodes(sampleTree) === 17;
```

## Exercise 4: Sum Even Tree Nodes

Use `%` to test whether the current value is even. Still recurse into both branches whether the current value is even or odd.

```ts
function sumEvenTreeNodes(root: TreeNode | undefined): number {
  // TODO: missing tree

  // TODO: sum the left and right branches

  // TODO: include root.value only when it is even
}
```

Expected checks:

```ts
sumEvenTreeNodes(undefined) === 0;
sumEvenTreeNodes({ value: 3 }) === 0;
sumEvenTreeNodes(sampleTree) === 14;
```

## Predict Before You Run

Before running checks, answer:

1. Which functions make one recursive call?
2. Which functions make two recursive calls?
3. Why does `factorial` need the return type `number | undefined`?
4. In `sumEvenTreeNodes`, why do odd nodes still need recursive calls?


## Extra Practice Bank

- `getAt(node: ListNode | undefined, index: number): string | undefined`: return the value at the index, or `undefined` when the index runs past the end.
- `reverseList(node: ListNode | undefined): ListNode | undefined`: return a new reversed chain. Do not mutate the original chain.
- `preorder(root: TreeNode | undefined): number[]`: visit current value, then left branch, then right branch.
- `inorder(root: TreeNode | undefined): number[]`: visit left branch, then current value, then right branch.
- `postorder(root: TreeNode | undefined): number[]`: visit left branch, then right branch, then current value.
- `treeHeight(root: TreeNode | undefined): number`: return `0` for an empty tree and `1 + max(leftHeight, rightHeight)` otherwise.
- `treeContains(root: TreeNode | undefined, target: number): boolean`: check the current value, then search left or right branches.
- `treeMaxValue(root: TreeNode | undefined): number | undefined`: return `undefined` for an empty tree, then combine current, left max, and right max.
- `countTreeNodes` variation: write expected outputs for an empty tree, a one-node tree, and an uneven tree before coding.

## Common Bugs

- Forgetting the empty-chain or empty-tree base case.
- Calling the same node again instead of `node.next`, `root.left`, or `root.right`.
- Forgetting one tree branch in the combine step.
- Multiplying by the result of `factorial(num - 1)` before checking whether it is `undefined`.
- Skipping odd nodes' branches in `sumEvenTreeNodes`.

## Bonus Puzzles

- Write `containsTree(root, target)` for numbers.
- Write `maxTreeValue(root)` and decide what it should return for an empty tree.
- Ask AI for a wrong `sumEvenTreeNodes` implementation and identify the bug.