104. Maximum Depth of Binary Tree

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

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

Solution

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

Modified Level Order Traversal - O(n) time - O(n) space

using namespace std;
 
class Solution {
public:
    int levels;
    void helper(TreeNode* node, int level) {
        if (levels == level) levels++;
        if (node->left != nullptr) helper(node->left, level +1);
        if (node->right != nullptr) helper(node->right, level +1);
    }
	int maxDepth(TreeNode* root) {
		if (root == nullptr) return 0;
        helper(root, 0);
		return levels;
	}
};

Improved Level Order Traversal - O(n) time - O(n) space

class Solution {
  public:
    int maxDepth(TreeNode *root) {
      if (root == nullptr) return 0;
      return max(1 + maxDepth(root -> left), 1 + maxDepth(root -> right));
    }
};

Tail Recursion

class Solution {
  private:
    // The queue that contains the next nodes to visit, 
    //   along with the level/depth that each node is located.
    queue<pair<TreeNode*, int>> next_items;
    int max_depth = 0;
    /**
     * A tail recursion function to calculate the max depth
     *   of the binary tree.
     */
    int next_maxDepth() {
      if (next_items.size() == 0) {
        return max_depth;
      }
 
      auto next_item = next_items.front();
      next_items.pop();
      auto next_node = next_item.first;
      auto next_level = next_item.second + 1;
      max_depth = max(max_depth, next_level);
 
      // Add the nodes to visit in the following recursive calls.
      if (next_node->left != NULL) {
        next_items.push(make_pair(next_node->left, next_level));
      }
      if (next_node->right != NULL) {
        next_items.push(make_pair(next_node->right, next_level));
      }    
      // The last action should be the ONLY recursive call
      //   in the tail-recursion function.
      return next_maxDepth();
    }
    
  public:
    int maxDepth(TreeNode* root) {
      if (root == NULL) return 0; 
      // Clear the previous queue.
      std::queue<pair<TreeNode*, int>> empty;
      std::swap(next_items, empty);
      max_depth = 0;
      // Push the root node into the queue to kick off the next visit.
      next_items.push(make_pair(root, 0));
      return next_maxDepth();
    }
};

Stack

We start from a stack that contains the root node and the corresponding depth which is 1. Then we proceed to the iterations: pop the current node out of the stack and push the child nodes. The depth is updated at each step.

class Solution {
  public:
  int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    vector<pair<int, TreeNode*>> my_stack;
    my_stack.push_back(pair<int, TreeNode*>(1, root));
    int max_depth = 0;
 
    while (!my_stack.empty()) {
      pair<int, TreeNode*> my_pair = my_stack.back();
      int c_depth = get<0>(my_pair);
      TreeNode* c_node = get<1>(my_pair);
      max_depth = max(max_depth, c_depth);
      my_stack.pop_back();
      if (c_node->left != NULL) {
        my_stack.push_back(pair<int, TreeNode*>(c_depth + 1, c_node->left));
      }
      if (c_node->right != NULL) {
        my_stack.push_back(pair<int, TreeNode*>(c_depth + 1, c_node->right));
      }
    }
    return max_depth;
  }
};