L12: Recursion II: Chains and Trees

Starter Types

Use these types and sample values for the exercises:

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.

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:

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.

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:

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.

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:

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.

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:

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.