# 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
}
``````