Minimum Depth of Binary Tree: recursive program always returns 0

Question

I am trying to do the LeetCode problem 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.

My code runs, but doesn't change the minimum depth value at all. I've asked my classmates and a teacher, but they don't know why it won't work either. I've spent a lot of time trying to figure it out.

This is my code:

class Solution {
public:
    int minHeight = 0, currHeight = 0;

    int minDepth(TreeNode* root) {
        searchTree(root);
        return minHeight;
    }

    void searchTree(TreeNode* p) {
        currHieght++;
        if (p->right == nullptr && p->left == nullptr) 
        {
            if (currHeight < minHeight) minHeight = currHeight--;
            return;
        }
        else if (p->right == nullptr)
            searchTree(p->left);
        else if (p->left == nullptr)
            searchTree(p->right);
        else
        {
            searchTree(p->left);
            searchTree(p->right);
            currHeight--;
        }

    }
};

Whatever the input, my code always returns 0. What am I doing wrong?

`if (currHeight < minHeight) minHeight = currHeight;` So `minHeight` always stuck at 0. — timrau, Oct 07 '22 at 17:58
Set `minHeight` to something big like `1000000000` at the beginning. As a general rule if you want minimum set its default value unrealistically big, so all numbers (heights) will be smaller, If you want maximum set the default to unrealistically small. — Botond Horváth, Oct 07 '22 at 18:14
*I've asked my classmates and a teacher but they don't know why it wont work either* -- And within a half-hour, StackOverflow provides the information that your "teacher" should have provided. Next time, don't rely on classmates or even your "teacher" -- instead, [debug](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) your code. — PaulMcKenzie, Oct 07 '22 at 18:26
Also, **do not post pictures of the code**. Copy the code as text and paste it in the edit window. — PaulMcKenzie, Oct 07 '22 at 18:29

trincot · Answer 1 · 2022-10-07T20:30:41.500

There are the following issues in your code:

minHeight is initialised as 0, so it could never get a greater value. This means whatever input your code gets, it will always return 0. minHeight should be set to an extremely great value, like INT_MAX, so that any leaf will have a lesser depth than that initial value.
The code has undefined behaviour when an empty tree is given as input. That boundary case should be checked.
currHeight is not always decreased when it should. Whatever the case in that if ...else if ... else if ... structure -- currHeight should be decreased. This is not done for the two middle cases. It will be better to perform this currHeight-- at a common place, at the end of the function body.

Here is your code with those corrections:

    int minHeight = INT_MAX, // Set at an extreme high value
        currHeight = 0;

    int minDepth(TreeNode* root) {
        if (root != nullptr) return 0; // boundary case: empty tree
        searchTree(root);
        return minHeight;
    }

    void searchTree(TreeNode* p) {
        currHeight++;
        if (p->right == nullptr && p->left == nullptr) 
        {
            // Don't increase currHeight here, but at a common spot in the code
            if (currHeight < minHeight) minHeight = currHeight;
        }
        else if (p->right == nullptr)
            searchTree(p->left);
        else if (p->left == nullptr)
            searchTree(p->right);
        else
        {
            searchTree(p->left);
            searchTree(p->right);
        }
        currHeight--; // Always do this

    }

Note that this is not the most efficient way to tackle the problem. This algorithm will visit all nodes, while a breadth-first traversal could stop as soon as a leaf is found.

Here is a spoiler solution using breadth-first traversal:

int minDepth(TreeNode* root) { if (root == nullptr) return 0; vector<TreeNode*> level, nextLevel; level.push_back(root); for (int depth = 1; true; depth++) { nextLevel.clear(); for (auto node : level) { if (node->left == nullptr && node->right == nullptr) return depth; // found the first leaf: solved! if (node->left != nullptr) nextLevel.push_back(node->left); if (node->right != nullptr) nextLevel.push_back(node->right); } level = nextLevel; // copy } }

Minimum Depth of Binary Tree: recursive program always returns 0

1 Answers1