Recently, I’ve learnt about a way of writing code which one might call “Leap Before You Look”. It helps you to craft more elegant solutions which automatically handle edge cases for you.

I first learnt about this style through this wonderful explanation video on Dynamic Programming by FreeCodecamp, where Alvin Zablan masterfully explains a recipe for tackling DP problems of every stripe.

In this post, I will illustrate the concept using three fairly common LeetCode problems, solved in TypeScript.

Spoiler alert! If you wish to solve them for yourself before proceeding, feel free to try them out first

Example One - Binary Tree Inorder Traversal

First, we have inorder traversal of a Binary Tree, using a recursive solution.

function inorderTraversal(root: TreeNode | null): number[] {
  let result = [];
  traverse(root, result);
  return result;
}

function traverse(node: TreeNode | null, result: number[]): void {
  if (node) {
    traverse(node.left, result);
    result.push(node.val);
    traverse(node.right, result);
  }
}

Notice here I’m NOT checking whether root is null before starting the recursion. Neither am I checking whether node is null to continue to recursion, inside the helper function. In short, I call the function regardless. The function checks itself, knows when to do nothing, complete, and lets the call stack return control back to the parent. Think about how much code you save writing there. Short and sweet.

Example Two - Maximum Depth of a Binary tree

Lest you think that the concept only applies when using Recursion, here’s another example of using it in for iterative code. Once again, if you haven’t solved this problem, or have not tried using an iterative approach, I encourage you to try before reading further.

function maxDepth(root: TreeNode | null): number {
  // use a stack of TypeScript tuples
  const stack: Array<[TreeNode | null, number]> = [];
  let maxDepth = 0; // init 0, store maxDepth as a global var

  stack.push([root, 1]);
  while (stack.length) {
    const [node, nodeDepth] = stack.pop();

    if (node) {
      // check if maxDepth needs updating
      maxDepth = Math.max(maxDepth, nodeDepth);
      // place children on stack to perform pre-order traversal of the tree
      // because the stack is LIFO, have to push right child first
      // copy nodeDepth to children so that they know the last state
      stack.push([node.right, nodeDepth + 1]);
      stack.push([node.left, nodeDepth + 1]);
    }
  }
  return maxDepth;
}

You can probably notice a few similar patterns here. One, I did not check whether root is null before pushing it into the stack. MaxDepth gets initialised to 0 anyway, and within the iteration, if root is null, no change happens and the 0 gets returned as the answer. Another thing which I deliberately left out was checking if node.right or node.left exists before pushing them onto the stack. It doesn’t matter. We can trust that the check is performed once the iteration reaches said node. Hopefully you are starting to see a pattern here.

Example Three - Reversing a Linked List/ LeetCode

In the third example, we deal with a different data structure - the Linked List.

function reverseList(head: ListNode | null): ListNode | null {
  // using the fact that current/ previous can either be null or ListNode
  // previous - current - next
  let current: ListNode = head;
  let previous: ListNode = null;
  // idea, traverse the linked list, and reversing the pointers
  // continue until no node, return the previous node which must have been the last one
  while (current) {
    let tmp = current.next;
    current.next = previous;
    // move pointers down
    previous = current;
    current = tmp;
  }
  return previous;
}

Notice that we always try to process the current node without bothering to check what the next node is. I.e., we are not looking whether to leap or not based on what the next node is. We just leap! And if there is nothing in the next node, then we are done. No need to prematurely do stuff like if next node is null, break etc. We’re taking advantage of the fact that both ends of the linked list point to null.

One observation is that the “Leap Before You Look” pattern comes in really handy for data structures that involves links between nodes. This can the Linked List, the Tree, or more generally speaking, any type of Graph. Which is to say that it can be applied to a wide variety of problems.

Hope you found this useful. Please feel free to reach out to me if you’d like to discuss more. Happy Coding, and till next time!