How to get the minimum height of a binary tree without using recursion?

Question

I've been stuck on this for some time now. This is what I have so far, but it gives the wrong result.

int get_min_height_iter(Node* r) {

    if (!r) return 0;

    std::queue<Node*> queue;
    queue.push(r);

    int count = 1;

    while (!queue.empty()) {

        Node* temp = queue.front();
        queue.pop();

        if (!temp->left || !temp->right)
            return count;

        ++count;

        queue.push(temp->left);
        queue.push(temp->right);

    }

    return -1;
}

Note that I can already do this function using recursion, I'm specifically interested in using queue or a stack. I can also get maximum height of the tree; I now need to make a function to get the minimum height.

For example in this case, the function should return 3, but it's returning 2:

int main() {

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->left->right->left = new Node(5);
    root->right->right = new Node(6);

    cout << get_min_height_iter(root);

    cin.get();
}

I know why it's doing it, I traced the code using a debugger, but I don't have much experience with binary trees and I don't know how to fix it. A hint would be greatly appreciated!

You push only node information to your stack. But you need to include the current value of count with the node information as well. Otherwise, when you pop a node, you don't know what the depth was at the time when that node was added to the stack. — jogojapan
– jogojapan, Commented Dec 18, 2013 at 3:20
root(1)->left(2)->left(empty) has a height of 2. However, as @jogojapan mentioned, this algorithm will not work well in other cases because you are not recording enough information. — jdigital
– jdigital, Commented Dec 18, 2013 at 3:22

Joe Z · Accepted Answer · 2013-12-18 05:50:35Z

2

You have three or four problems:

You need to push the rank (depth) of each node with the nodes themselves onto the queue. You can use std::pair<> to bundle that information if you don't have place for it elsewhere. If the node structure has a "depth" or "rank" member, you can simply update that.
Your problem statement requires you to measure depth, not count nodes. The depth of a given node is equal to the depth of its parent plus one. Your loop currently counts nodes.
Only push children on the queue if they exist.
If min depth is specified as the shortest path to a node with no descendents, then your "if () return" condition should look for left and right being null, not left or right being null.

edited Dec 18, 2013 at 5:50

answered Dec 18, 2013 at 3:22

Joe Z

18k3 gold badges30 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to get the minimum height of a binary tree without using recursion?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related