Leetcode: 104. Maximum Depth of Binary Tree

Calculating the Maximum Depth of a Binary Tree in C++

Introduction

In this blog post, we will discuss the implementation of an algorithm to calculate the maximum depth of a binary tree. We will provide a step-by-step explanation of the code and discuss its complexity analysis. Additionally, we will explore a tail recursion approach to optimize the calculation process. Let's dive into the details!

Problem Statement

Given the root of a binary tree, we need to calculate the maximum depth of the tree. The maximum depth is defined as the number of nodes along the longest path from the root node to any leaf node.

Solution Overview

To calculate the maximum depth of a binary tree, we can use a recursive approach. Starting from the root node, we traverse the tree and increment the depth as we go deeper into the tree. We compare the depth at each node with the maximum depth encountered so far and update it if necessary. By the end of the traversal, we obtain the maximum depth of the binary tree.

Solution Implementation

/**
 * 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) {}
 * };
 */
class Solution {

  private:
    // The queue that contains the next nodes to visit, 
    //   along with the level/depth that each node is located.
    queue> 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> 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();
    }
};
  

The class Solution contains the implementation of the maxDepth function, which takes the root of the binary tree as input and returns the maximum depth of the tree.

The algorithm uses a tail recursion approach to calculate the maximum depth. It maintains a queue, next_items, to store the nodes to visit along with their corresponding levels/depths. Additionally, it keeps track of the maximum depth encountered so far using the max_depth variable.

The next_maxDepth function is a tail recursion function that performs the calculation. It retrieves the next node and level from the queue, updates the maximum depth if necessary, and adds the child nodes to the queue for further traversal. The function calls itself recursively until all nodes are processed.

Finally, the maxDepth function initializes the queue and maximum depth variables, and starts the tail recursion by pushing the root node into the queue. It returns the result obtained from the next_maxDepth function.

Conclusion

In this blog post, we explored an algorithm to calculate the maximum depth of a binary tree in C++. The tail recursion approach provided an efficient solution to traverse the tree and determine the maximum depth. We provided a step-by-step explanation of the code and discussed its complexity analysis.