Maximum Depth of Binary Tree

Loading...LeetCode

Problem

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Pseudocode

simple dfs traversal
    - if no node return
    - recurse
    - return + 1

Solution

var maxDepth = function (root) {
  function walk(node) {
    if (!node) {
      return 0;
    }

    // pre
    // recurse
    let leftDepth = walk(node.left);
    let rightDepth = walk(node.right);
    // post

    // this is the increment
    return Math.max(leftDepth, rightDepth) + 1;
  }

  return walk(root);
};

Time and Space Complexity

Time

• traverse trough all the child nodes to find the deepest node - O(N)

• Total - O(N)

Space

• maximum memory requirement for traversing a BT - O(height)

• Total - O(height)