My solution to minimum depth of binary tree


  • 0
    Z
     int minDepth(TreeNode *root) {
        if (root == NULL)
        {
            return 0;
        }
        
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        
        if (left == 0 && right == 0) // leaf
        {
            return 1;
        } else if (left == 0) 
        {
            return 1 + right;
        } else  if (right == 0)
        {
            return 1 + left;
        } else
        {
            return 1 + min(left, right);
        }
    }
    

    My solution is O(n) in time and O(1) in space. This is done using pre-order traversal, where we recurse through the whole tree and then determine what the minimum depth would be.

    Can we do any better?


  • 1
    V

    Yes.Time Complexity in the average case can be reduced by pruning the tree when required. The following code shows it.

    class Solution {
    private:
        int min_depth = 10000;
    public:
        void minHelper(TreeNode *root, int depth)
        {
            if(depth >= (min_depth))
                return;
            if(root->left == NULL && root->right==NULL)
            {
                min_depth = depth+1;
                return;
            }
            if(root->left)
                minHelper(root->left, depth+1);
            if(root->right)
                minHelper(root->right, depth+1);
        }
    
        int minDepth(TreeNode *root) {
             if(root == NULL)
                return 0;
            minHelper(root, 0);
            return min_depth;
        }
    };
    

  • 0
    F

    There is no O(1) space solution with recursion.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.