Minimum Depth of Binary Tree

class Solution {
public:
    int minimumDepth(TreeNode* rootNode) {
        if (!rootNode) return 0;

        queue<TreeNode*> nodesQueue;
        nodesQueue.push(rootNode);
        int level = 1;

        while (!nodesQueue.empty()) {
            int levelSize = nodesQueue.size();

            while (levelSize--) {
                TreeNode* currentNode = nodesQueue.front();
                nodesQueue.pop();

                if (!currentNode) continue;

                if (!currentNode->left && !currentNode->right) {
                    return level;
                }

                nodesQueue.push(currentNode->left);
                nodesQueue.push(currentNode->right);
            }

            level++;
        }

        return -1;
    }
};

The solution implements the Breadth-First Search (BFS) algorithm to determine the minimum depth of a binary tree in C++. Here's a breakdown of the approach:

• Initial Check: If the rootNode is nullptr, return 0. This indicates that the tree does not exist.

• Queue Initialization: A queue of TreeNode* is used to store the nodes of the tree level by level.

• Iterate Through Levels: Start with the root node and initialize level to 1 to represent the root level. Use a while loop to process all nodes level by level until the queue is empty.

• Process Each Level:

  • Determine the number of nodes (levelSize) at the current level using queue.size().
  • Use a nested loop to process each node at the current level:
    • Dequeue the front node from queue.
    • Check if the dequeued node is a leaf (both left and right children are nullptr). If true, return the current level as it represents the minimum depth of the tree.
    • If the node has children, enqueue them to the queue.
  • After processing all nodes at a level, increment the level.

• Fallback: If the loop completes without finding a leaf, return -1. This serves as a fallback although theoretically, it should never trigger if the input tree is valid.

By the conclusion of this process, the minimumDepth function accurately returns the minimum depth of the binary tree, which is the number of nodes along the shortest path from the root node down to the nearest leaf node.

class Solution {
    public int getMinimumDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();

                if (currentNode == null) continue;

                if (currentNode.left == null && currentNode.right == null) {
                    return level;
                }

                queue.offer(currentNode.left);
                queue.offer(currentNode.right);
            }
            level++;
        }
        return -1;
    }
}

This Java program assumes the role of finding the minimum depth of a binary tree. The code defines a class named Solution with a method getMinimumDepth which takes the root of the binary tree as its parameter.

• Initialize a check for if the root is null. If true, return 0 indicating the tree has no nodes.
• Create a Queue to store the nodes of the tree, using Java's LinkedList to manage the queue operations.
• Offer the root node to the queue and initialize a variable level at 1 to track the depth of the tree.
• Iterate over the queue with a while loop until the queue is empty.
  • Determine the number of elements (size) at the current depth by checking the size of the queue at the start of the loop iteration.
  • Iterate over these elements using a for loop:
    • Poll the currentNode from the queue.
    • If currentNode is null, continue to the next iteration.
    • Check if currentNode is a leaf node (both left and right children are null). If it is, return the current level as this is the minimum depth of the tree.
    • Offer both the left and right children of currentNode to the queue.
  • Increment the level after processing all nodes at the current depth.
• Following the loop, the method returns -1. This line will theoretically never execute since a null tree is handled at the start, and a valid tree would eventually find a leaf node and exit from the loop. Thus, -1 serves as a fallback return value indicating an unexpected behavior in the tree traversal logic.

struct DataQueue {
    struct TreeNode* element;
    struct DataQueue* nextNode;
};
struct QueueStructure {
    struct DataQueue* front;
    struct DataQueue* rear;
    int count;
};
void enqueue(struct QueueStructure* queue, struct TreeNode* treeNode) {
    struct DataQueue* tempNode = malloc(sizeof(struct DataQueue));
    tempNode->element = treeNode;
    tempNode->nextNode = NULL;
    if (!queue->front) {
        queue->front = tempNode;
        queue->rear = tempNode;
    } else {
        queue->rear->nextNode = tempNode;
        queue->rear = tempNode;
    }
    queue->count++;
}
struct TreeNode* dequeue(struct QueueStructure* queue) {
    struct DataQueue* tmpNode = queue->front;
    struct TreeNode* treeNode = tmpNode->element;
    queue->front = tmpNode->nextNode;
    if (!queue->front) {
        queue->rear = NULL;
    }
    free(tmpNode);
    queue->count--;
    return treeNode;
}
bool isQueueEmpty(struct QueueStructure* queue) { return queue->count == 0; }

int minimumDepth(struct TreeNode* rootNode) {
    if (!rootNode) {
        return 0;
    }
    struct QueueStructure queue = {0};
    enqueue(&queue, rootNode);
    int depthLevel = 1;
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.count;
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* current = dequeue(&queue);
            // Return depthLevel when reaching the first leaf node.
            if (!current->left && !current->right) {
                return depthLevel;
            }
            if (current->left) {
                enqueue(&queue, current->left);
            }
            if (current->right) {
                enqueue(&queue, current->right);
            }
        }
        depthLevel++;
    }
    return -1; // If no leaf node is found, should theoretically never happen.
}

The provided C code defines a solution for finding the minimum depth of a binary tree using a breadth-first search (BFS) approach. Below is the step-by-step breakdown of the solution.

• Data Structure Definitions:

  • DataQueue is used to manage individual tree nodes within the queue.
  • QueueStructure manages the queue with pointers to the first (front) and last (rear) elements and a counter (count) for the number of elements.

• Queue Operations:

  • enqueue function adds a new TreeNode to the end of the queue.
  • dequeue function removes a TreeNode from the front of the queue and returns it.
  • isQueueEmpty checks if the queue is empty by evaluating if the count is zero.

• Algorithm for Minimum Depth Calculation (minimumDepth function):

  • Begin by checking if the rootNode is NULL. If true, return 0 because an empty tree has a depth of zero.
  • Initialize a QueueStructure and enqueue the rootNode.
  • Start with depthLevel set to 1. This level accounts for the root node.
  • Utilize a while loop to process levels of the tree as long as the queue is not empty:
    • Determine the number of nodes at the current depth (levelSize).
    • Iterate over each node in the current level:
      • Dequeue the node.
      • If the dequeued node is a leaf (no left or right child), return the depthLevel as this indicates the shallowest leaf has been reached.
      • If the node has a left child, enqueue it.
      • If the node has a right child, enqueue it.
    • Increment depthLevel after processing all nodes at the current depth.
  • Return -1 if no leaf node is found, which theoretically shouldn't happen since the function would have returned upon finding the first leaf.

This method efficiently finds the minimum tree depth by processing levels gradually and stopping early upon finding the first leaf. The use of BFS ensures shortest path discovery, beneficial for determining the minimum depth in potentially unbalanced trees.

var findMinDepth = function (treeNode) {
    if (!treeNode) {
        return 0;
    }
    let nodesQueue = [treeNode];
    let levelDepth = 1;
    while (nodesQueue.length) {
        let levelLength = nodesQueue.length;
        for (let i = 0; i < levelLength; i++) {
            let currentNode = nodesQueue.shift();
            if (!currentNode) {
                continue;
            }
            if (!currentNode.left && !currentNode.right) {
                return levelDepth;
            }
            nodesQueue.push(currentNode.left);
            nodesQueue.push(currentNode.right);
        }
        levelDepth++;
    }
    return -1;
};

The provided JavaScript function, findMinDepth, determines the minimum depth of a binary tree. The function follows these steps to calculate and return the result:

1. If the treeNode input is null, returning 0 indicates that an empty tree has a depth of zero.
2. Initialize a queue with the root node treeNode and set the initial tree depth to 1.
3. Use a while loop to traverse the tree level by level until there are no more nodes in the queue:
   • Determine the number of nodes at the current depth level using levelLength.
   • Iterate through each node at the current level:
     • Remove the node from the front of the queue.
     • If the node is not null, check if it is a leaf node (i.e., it has no left or right child). If it is a leaf node, return the current levelDepth as this represents the minimum depth of the tree.
     • If not a leaf, enqueue the left and right children of the current node to the queue.
   • After iterating through the current level, increase the levelDepth by 1 for the next level of nodes.
4. If the loop exits without finding a leaf node (though theoretically this would not happen with a valid non-empty input tree), return -1.

This solution efficiently uses a Breadth-First Search (BFS) approach, evaluating the tree level by level to quickly find the shallowest leaf node. This ensures that the minimum depth is found as soon as it is encountered during the traversal.

class Solution:
    def minimumDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        nodes = collections.deque([root])
        level = 1
        while nodes:
            level_size = len(nodes)
            for _ in range(level_size):
                current = nodes.popleft()
                if not current:
                    continue
                if not current.left and not current.right:
                    return level
                nodes.append(current.left)
                nodes.append(current.right)
            level += 1
        return -1

The solution provided calculates the minimum depth of a binary tree using a breadth-first search (BFS) approach. The solution is implemented in Python 3 and utilizes a queue to traverse through the nodes at each level of the tree.

• The function starts by checking if the root node is None. If it is, the function returns 0, indicating that the tree has no depth.
• A queue (double-ended queue) initializes with the root node, and the depth level starts at 1.
• A while loop continues as long as there are nodes in the queue. Inside the loop:
• The number of nodes at the current level is determined by len(nodes).
• The loop then iterates over these nodes, dequeuing each node and checking:
  • If the node is None, it skips to the next node.
  • If the node is a leaf node (both left and right children are None), it returns the current level as this represents the minimum depth of the tree up to that leaf.
  • If the node has children, they are added to the queue to be processed in the next levels.
• The level is incremented after each level has been fully processed.

If all nodes are processed and no leaf node has been reached prematurely, the function would theoretically return -1, although this scenario isn't possible given the nature of the problem (every non-empty tree has at least one leaf).

The BFS approach ensures that the first leaf node encountered is at the minimum depth, efficiently determining the answer without the need to explore the entire tree.