Minimum Depth of Binary Tree by using Recursive Depth First Search and Iterative Breadth First Search Algorithms

ACMer

11 years ago

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:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

Try to find the minimal depth of the tree, that is the shortest distance from root node to any leaf nodes.

To find out the minimum depth of a binary tree, we can use the DFS (Depth First Search) Algorithm or Breadth First Search (BFS) Algorithm.

Depth First Search Algorithm to Compute the Minimum Depth of a Binary Tree

DFS is usually implemented in Recursive manner. The code below is intuitive – from top-down as we traverse the tree from root to the leaves.

class Solution {
public:
    int minDepth(TreeNode *root) {
        // empty tree depth = 0
        if (root == NULL) return 0;
        // leaf node depth = 1
        if ((root->left == NULL) && (root->right == NULL)) return 1;
        // only right sub-tree
        if (root->left == NULL) return minDepth(root->right) + 1;
        // only left sub-tree
        if (root->right == NULL) return minDepth(root->left) + 1;
        // depth of left tree
        int left =  minDepth(root->left);
        // depth of right tree
        int right = minDepth(root->right);
        // return the smaller one
        return min(left, right) + 1;
    }
};

class Solution {
public:
    int minDepth(TreeNode *root) {
        // empty tree depth = 0
        if (root == NULL) return 0;
        // leaf node depth = 1
        if ((root->left == NULL) && (root->right == NULL)) return 1;
        // only right sub-tree
        if (root->left == NULL) return minDepth(root->right) + 1;
        // only left sub-tree
        if (root->right == NULL) return minDepth(root->left) + 1;
        // depth of left tree
        int left =  minDepth(root->left);
        // depth of right tree
        int right = minDepth(root->right);
        // return the smaller one
        return min(left, right) + 1;
    }
};

However, when the tree has a relatively large depth, this may overflow the stack, which is the inherent problem/disadvantage of all recursion methods. This can be avoided by rewriting the recursion using queues (manually pushing and popping the stacks). The biggest advantage of recursion algorithms is its quickness in implementation, usually in just a few lines of code which can clearly describe the algorithm.

The recursions may be slow, due to two reasons: first, the recursion calls yield overhead to create stacks to preserve the states/parameters. Second, there will be duplicates in obtaining intermediate values i.e. values may be re-calculated, which is time wasting.

Breadth First Search Algorithm to Compute the Minimum Depth of a Binary Tree

The BFS algorithm traverse the tree level-by-level, then if we first meet a leaf node, we know we have the minimum depth (shortest distance from root to the leaf).

/**
 * 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 {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 1});
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left == p.first->right) {
                return p.second;
            }
            if (p.first->left) q.push({p.first->left, p.second + 1});
            if (p.first->right) q.push({p.first->right, p.second + 1});
        }
        return 0;
    }
};

/**
 * 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 {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 1});
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left == p.first->right) {
                return p.second;
            }
            if (p.first->left) q.push({p.first->left, p.second + 1});
            if (p.first->right) q.push({p.first->right, p.second + 1});
        }
        return 0;
    }
};

Here, the BFS implemnation pushes children nodes and their corresponding depths to the queue so that we can immediately return the shortest depth when we find a leaf node. The time and space complexity is O(N) where N is the number of the nodes in the binary tree.

Another BFS implementation would be slightly different:

/**
 * 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 {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int d = 0;
        while (!q.empty()) {
            auto sz = q.size();
            d ++;
            for (int i = 0; i < sz; ++ i) {
                auto p = q.front();
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
                if (p->left == p->right) return d;
                q.pop();
            }
        }
        return d;
    }
};

/**
 * 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 {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int d = 0;
        while (!q.empty()) {
            auto sz = q.size();
            d ++;
            for (int i = 0; i < sz; ++ i) {
                auto p = q.front();
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
                if (p->left == p->right) return d;
                q.pop();
            }
        }
        return d;
    }
};

In above Breadth First Search code, we expand all the children nodes (of the same level) and increment the level until we reach the first leaf node which means it is the closest leaf node to the root.

–EOF (The Ultimate Computing & Technology Blog) —

833 words
Last Post: Coding Exercise – Palindrome Number - C++ - Online Judge
Next Post: Coding Exercise - Implement Pow(x, n) - C++ - Online Judge

The Permanent URL is: Minimum Depth of Binary Tree by using Recursive Depth First Search and Iterative Breadth First Search Algorithms (AMP Version)

Depth First Search Algorithm to Compute the Minimum Depth of a Binary Tree

Breadth First Search Algorithm to Compute the Minimum Depth of a Binary Tree

Related posts: