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

## more LeetCode posts Design HashSet solution using TypeScript Fizz Buzz solution using TypeScript Pascal's Triangle solution using TypeScript Min Stack solution using TypeScript Symmetric Tree solution using TypeScript Same Tree solution using TypeScript