Maximum Depth of Binary Tree

class Solution {
  public:
  int maximumDepth(TreeNode* node) {
    if (node == NULL) {
      return 0;
    }

    vector<pair<int, TreeNode*>> stack;
    stack.push_back(make_pair(1, node));
    int deepest = 0;
    while (!stack.empty()) {
      pair<int, TreeNode*> current = stack.back();
      int currentDepth = current.first;
      TreeNode* currentNode = current.second;
      deepest = max(deepest, currentDepth);
      stack.pop_back();
      if (currentNode->left != NULL) {
        stack.push_back(make_pair(currentDepth + 1, currentNode->left));
      }
      if (currentNode->right != NULL) {
        stack.push_back(make_pair(currentDepth + 1, currentNode->right));
      }
    }
    return deepest;
  }
};

This solution outlines an approach to compute the maximum depth of a binary tree using C++ programming. The method used here is a depth-first search (DFS), leveraging an iterative strategy with a stack to avoid recursion.

This function maximumDepth in the Solution class determines the depth of the given binary tree by:

• Checking if the input node (TreeNode* node) is NULL. If true, it returns 0, indicating that the tree is empty, so there is no depth to measure.

• Initializing a vector of pairs, stack, which will store each node along with its corresponding depth level. The stack helps in iterating through the tree iteratively without using recursion.

• Starting with the root node, the code pushes the node and its depth level (starting at 1) onto the stack.

• A while loop is utilized wherein each node is processed as long as the stack is not empty:

  • The node at the top of the stack is evaluated.
  • The current depth of this node is compared with the maximum depth found so far (deepest) and updated if necessary.
  • The node is then removed from the stack.
  • The function then checks if the current node has left or right children. If so, these child nodes along with their depth level (current depth + 1) are pushed onto the stack.

• After the while loop finishes (i.e., the stack is empty and all nodes have been evaluated), the function returns the value of deepest, which now contains the maximum depth of the binary tree.

This procedure efficiently handles the depth determination using a non-recursive method, ensuring that each node is visited only once and keeping track of the depth without additional memory overhead common in recursive solutions.

class Solution {
    public int findMaxDepth(TreeNode node) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        LinkedList<Integer> depthCounts = new LinkedList<>();
        if (node == null) return 0;

        nodes.add(node);
        depthCounts.add(1);

        int maxDepth = 0, currentLevelDepth = 0;
        while (!nodes.isEmpty()) {
            node = nodes.pollLast();
            currentLevelDepth = depthCounts.pollLast();
            if (node != null) {
                maxDepth = Math.max(maxDepth, currentLevelDepth);
                nodes.add(node.left);
                nodes.add(node.right);
                depthCounts.add(currentLevelDepth + 1);
                depthCounts.add(currentLevelDepth + 1);
            }
        }
        return maxDepth;
    }
}

The provided Java implementation demonstrates how to calculate the maximum depth (or height) of a binary tree using a breadth-first search approach. Here's a concise breakdown of how this solution operates:

• A helper class, TreeNode, is expected to be defined elsewhere, which represents the tree nodes. Each TreeNode should have a left and right child.

• The main method in the Solution class, findMaxDepth, takes the root TreeNode of the binary tree as a parameter.

• Two LinkedList instances are used:

  • nodes holds the tree nodes to be traversed.
  • depthCounts keeps track of the depth levels corresponding to each node in the nodes list.

• Initially, the root node is added to nodes if it is not null, and 1 (indicating the starting depth level) is added to depthCounts.

• The method then enters a loop that continues until there are no more nodes to process in the nodes list:

  • The last node and its depth count are removed from their respective lists.
  • If the node being processed is not null, the method calculates the maximum depth encountered so far.
  • The node’s children (left and right) are added to the nodes list, and their corresponding depth counts (current node's depth + 1) are added to the depthCounts list.

• The loop ensures that all nodes in the tree are visited, and for each node, the depth is correctly computed and potentially updated if it exceeds the previously recorded maximum depth.

• After the loop concludes, the highest value recorded in maxDepth is returned as the maximum depth of the binary tree.

This implementation efficiently traverses the tree without recursively calling the function, thus potentially reducing stack space usage, which is particularly beneficial for trees with high depths.

struct Item {
    struct TreeNode* itemNode;
    int itemDepth;
};
struct Item* create_item(struct TreeNode* node, int depth) {
    struct Item* newItem = malloc(sizeof(struct Item));
    newItem->itemNode = node;
    newItem->itemDepth = depth;
    return newItem;
}
int calculateMaxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    struct Item** nodeStack = malloc(10000 * sizeof(struct TreeNode*));
    int stackPointer = 0;
    nodeStack[stackPointer++] = create_item(root, 1);
    int deepest = 0;
    while (stackPointer != 0) {
        struct Item* currentItem = nodeStack[--stackPointer];
        int currentDepth = currentItem->itemDepth;
        struct TreeNode* currentNode = currentItem->itemNode;
        deepest = currentDepth > deepest ? currentDepth : deepest;
        free(currentItem);
        if (currentNode->left != NULL) {
            nodeStack[stackPointer++] = create_item(currentNode->left, currentDepth + 1);
        }
        if (currentNode->right != NULL) {
            nodeStack[stackPointer++] = create_item(currentNode->right, currentDepth + 1);
        }
    }
    free(nodeStack);
    return deepest;
}

This C language code determines the maximum depth of a binary tree using an iterative approach with a custom stack. It begins by defining a structure Item, which encapsulates a tree node and its depth. Here's an overview of the process:

• A helper function create_item initializes and returns a new Item containing a node and its depth.
• The function calculateMaxDepth calculates the tree's maximum depth:
  1. If the root is null, it returns 0, indicating an empty tree.
  2. Initializes a stack to store nodes as they are processed.
  3. Uses a loop to process each node in the stack. For the current node, if it is deeper than previously encountered nodes, it updates the deepest variable.
  4. Nodes are explored depth-first, and their children are added to the stack with incremented depth.

Finally, the code handles memory correctly by dynamically allocating space for the stack and items, and freeing them once done processing. This efficient implementation ensures that the maximum depth of the tree is determined without using recursion, which can be advantageous for handling large trees or to avoid stack overflow in environments with limited stack size.

var calculateDepth = function (treeRoot) {
    let nodeStack = [];
    if (treeRoot != null) nodeStack.push({ node: treeRoot, current_depth: 1 });
    let maxDepth = 0;
    while (nodeStack.length > 0) {
        let { node, current_depth } = nodeStack.pop();
        if (node) {
            maxDepth = Math.max(maxDepth, current_depth);
            nodeStack.push({ node: node.left, current_depth: current_depth + 1 });
            nodeStack.push({ node: node.right, current_depth: current_depth + 1 });
        }
    }
    return maxDepth;
};

This article provides a solution for finding the maximum depth of a binary tree using JavaScript. The function calculateDepth takes treeRoot as its parameter, which represents the root of the binary tree.

• Start with an empty nodeStack array designed to keep track of nodes and their respective depths.
• Push the root node into nodeStack if it's not null, with an initial depth of 1.
• Initialize maxDepth to zero to hold the record of the deepest point reached in the tree.
• Use a while loop to process each node in the stack until the stack is empty. During each iteration, pop the top node from the stack and:
  • Update maxDepth using Math.max to compare the current maximum depth and the depth of the current node.
  • Push the left and right children of the current node onto the stack. Increase the depth by 1 for each child.
• Once the loop completes, return maxDepth as the solution.

By the end, the function returns the maximum depth of the binary tree, which is determined by the highest level reached by any node in the tree structure. This approach uses a stack to simulate recursive tree traversal, ensuring all nodes are examined.

class Solution:
    def maxDepth(self, node: TreeNode) -> int:
        nodes = []
        if node:
            nodes.append((1, node))

        max_depth = 0
        while nodes:
            depth, node = nodes.pop()
            if node:
                max_depth = max(max_depth, depth)
                nodes.append((depth + 1, node.left))
                nodes.append((depth + 1, node.right))

        return max_depth

The provided Python3 code defines a method maxDepth for calculating the maximum depth of a binary tree. Here's the breakdown of the code's functionality:

• Define a class named Solution.
• Inside Solution, define the maxDepth method that accepts a node parameter, which refers to the root node of a binary tree.
• Initialize an empty list nodes to keep track of nodes to be explored along with their depth levels.
• Check if the root node exists. If it does, add the root node and its depth level (1) to the nodes list.
• Set max_depth to 0, which will store the maximum depth as the algorithm progresses.
• Implement a while loop that runs as long as there are nodes left in the nodes list. This loop helps in exploring each node:
  • Pop the last entry from nodes to get the current node and its depth.
  • If the current node is not None, compare its depth with max_depth and update max_depth if the current node's depth is greater.
  • Add child nodes (left and right) of the current node to the nodes list, with their depth incremented by 1.
• Once there are no nodes left to explore, return the value of max_depth, which is the maximum depth of the binary tree.

The method essentially performs a depth-first search of the binary tree using a stack (implemented with a list nodes), tracking the maximum depth encountered throughout the traversal.