# 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

*represents the number of nodes in the tree.*

**n****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
}
```