111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

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

Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]

Output: 5

Constraints:

• The number of nodes in the tree is in the range [ 0 , 1 0 5 ] [0, 10^5] [0,105].
• -1000 <= Node.val <= 1000

  From: LeetCode

  Link: 111. Minimum Depth of Binary Tree

  ---

  Solution:

  Ideas:

  • TreeNode and QueueNode Structures: We define a TreeNode structure for the binary tree nodes and a QueueNode structure for the BFS queue.
  • newTreeNode and newQueueNode Functions: These functions create new nodes for the tree and the queue.
  • BFS Implementation in minDepth: We use a queue to perform BFS. For each node, we check if it’s a leaf. If it is, we return its depth. If not, we enqueue its children with their respective depths.
  • Main Function: Demonstrates how to use the minDepth function and free the allocated memory for the binary tree.

    Code:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct QueueNode {
        struct TreeNode *node;
        int depth;
        struct QueueNode *next;
    };
    // Function to create a new tree node
    struct TreeNode* newTreeNode(int val) {
        struct TreeNode *temp = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        temp->val = val;
        temp->left = temp->right = NULL;
        return temp;
    }
    // Function to create a new queue node
    struct QueueNode* newQueueNode(struct TreeNode *node, int depth) {
        struct QueueNode *temp = (struct QueueNode *)malloc(sizeof(struct QueueNode));
        temp->node = node;
        temp->depth = depth;
        temp->next = NULL;
        return temp;
    }
    // Function to perform BFS and find the minimum depth
    int minDepth(struct TreeNode* root) {
        if (root == NULL) return 0;
        // Initialize the queue
        struct QueueNode *front = newQueueNode(root, 1);
        struct QueueNode *rear = front;
        // Perform BFS
        while (front != NULL) {
            struct TreeNode *currentNode = front->node;
            int currentDepth = front->depth;
            // Check if it's a leaf node
            if (currentNode->left == NULL && currentNode->right == NULL) {
                return currentDepth;
            }
            // Enqueue left child
            if (currentNode->left != NULL) {
                rear->next = newQueueNode(currentNode->left, currentDepth + 1);
                rear = rear->next;
            }
            // Enqueue right child
            if (currentNode->right != NULL) {
                rear->next = newQueueNode(currentNode->right, currentDepth + 1);
                rear = rear->next;
            }
            // Dequeue the front node
            struct QueueNode *temp = front;
            front = front->next;
            free(temp);
        }
        return 0; // This line should never be reached
    }
    // Function to free the binary tree
    void freeTree(struct TreeNode *root) {
        if (root == NULL) return;
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }