Maximum Depth of Binary Tree solution using TypeScript

This post outlines my TypeScript solution to the LeetCode "Maximum Depth of Binary Tree" question using an iterative approach.

Algorithm: The algorithm completes a depth-first traversal of the tree and finds it's maximum depth by completing the following steps:

• Create a new Stack. Because this written in TypeScript, a Stack data structure will be represented by a typed array.
• Each node on the Stack should reference a TreeNode, and it's depth in the tree.
• Push the root node to the Stack, giving it a depth of 1.
• Traverse each node in the tree by doing the following until the Stack is empty:
  • Pop a node off the Stack.
  • See if it's the deepest node found so far.
  • If it has children, set their depth, and push them to the Stack.
• When no more items are on the Stack, the max depth can be returned.

Time Complexity: Because each node in the tree will be visited only one time, the time complexity is O(n) where n represents the number of nodes in the tree.

Space Complexity: In the worst case, a completely unbalanced tree, the space complexity will be O(n). In the average case, a balanced tree, the space complexity will be O(log(n)).

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
/**
 * Maximum Depth of Binary Tree
 * Given a binary tree, find its maximum depth.
 * The maximum depth is the number of nodes along 
 * the longest path from the root node down to the 
 * farthest leaf node.
 *
 * Time Complexity: O(n)
 * Space Complexity: 
 *   O(n) in worst case (completely unbalanced)
 *   O(log(n)) in average case (balanced)
 *
 * Input: 3    Output: 3
 *       / \
 *      9  20
 *        /  \
 *       15   7
 */
function maxDepth(root: TreeNode | null): number {
    // create a stack and push the root node to it
    const stack: StackNode[] = [
        { node: root, depth: 1 }
    ];
    // max depth found so far
    let max = 0;
    /*
     * On each iteration, pop a TreeNode off the stack and
     * push it's children back onto the stack, keeping track
     * of each TreeNodes depth along the way. Every time
     * a TreeNode is popped off the stack, see if it is the 
     * deepest node found so far.
     */
    while (stack.length) {
        const {node, depth} = stack.pop() as StackNode;
        if (node) {
            max = Math.max(depth, max);
            stack.push({ node: node.left, depth: depth + 1 });
            stack.push({ node: node.right, depth: depth + 1 });
        }
    }
    return max;
}

/**
 * Represents a Node in the Stack.
 * Used to track TreeNodes and their depth in the tree
 */
type StackNode = {
    node: TreeNode | null,
    depth: number
}