Non recursive Program to find minimum height of Binary tree

Question

I know the recursive code could be written for finding the minimum height. But for a very large tree (like million nodes in leftside vs 1 node in right side) - the approach isn't good. So please let me know if following code is fine, it uses BFS:-

    if (root == null)
    {
        return 0;
    }

    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);
    int min = 0;

    while (queue.Count > 0)
    {                
        Node temp = queue.Dequeue();

        if (temp.LeftChild == null)
        {
            return ++min;
        }
        if (temp.LeftChild != null)
        {
            ++min;
            queue.Enqueue(temp.LeftChild);
        }

        if (temp.RightChild == null)
        {
            return ++min;
        }
        if (temp.RightChild != null)
        {
            ++min;
            queue.Enqueue(temp.RightChild);
        }
    }

    return 0;

So for a tree like

The above returns 1, (as per Floor(Log(n))?

Thanks.

For the million node case, what about recursion isn't good? Are you worried about runtime performance, exhausting the stack, or something else? — razeh
– razeh, Commented Aug 12, 2012 at 20:53
it's more performance (& exhausting the stack) - if I can find the leaf node quickly, why do i have to traverse the entire tree. (return 1 + Math.Min(GetMin(root.LeftNode) , GetMin(root.RightNode)); — parsh
– parsh, Commented Aug 12, 2012 at 21:07

dvvrd · Accepted Answer · 2012-08-13 15:27:52Z

1

The idea is perfect. But the code still can be bettered a bit.

Why do you increase min every time you dequeue item? And you do it twice, it is two times worse :) If you supose this variable to be nodes counter then it is incorrect too because you did not count root element. And hence it must be called in the other way, not min.
Why do you check if children are null twice? If statements spoil the pipe, their count must be minimized.

The idea is next. Let`s call the row of the nodes of the equal level full if every node in it has both children. Then min height is the count of full rows in the tree. It equals closest power index of 2 to the items count in all the full rows + 1. A code:

if (root == null)
{
    return 0;
}

Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
int nodesCount = 0;

while (queue.Count > 0)
{                
    Node temp = queue.Dequeue();

    if (temp.LeftChild == null || temp.RightChild == null)
    {
        return Floor(Log(nodesCount + 1)/Log(2)); // It can be made much better using, for example, bitwise operations but this is not the question`s topic
    }

    ++nodesCount;
    queue.Enqueue(temp.LeftChild);
    queue.Enqueue(temp.RightChild);
}

return Infinity; // :)

answered Aug 13, 2012 at 15:27

dvvrd

1,68912 silver badges20 bronze badges

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

2 Comments

parsh Over a year ago

Thanks for the soln. My bad, didn't clean up the code before posting. Will keep that in mind. Anyways, great points for writing clean code :-). But I have a follow up q, why does a recursive return value = 2 for the above tree. Please correct me if i am wrong. if (root == null) return 0; return Math.Floor(1 + Math.Min(MinHeight(root.LeftChild), MinHeight(root.RightChild)));

dvvrd Over a year ago

@parsh: This is because you step into 1 extra level. You return 0 if current child is null. This is wrong point because we have 0 height when current child has no at least one of his child. That`s why you get height 1 when you getting into 3rd node and 2 when come back into the root

louis.luo · Accepted Answer · 2012-08-14 07:13:45Z

0

Use 2 stacks to do a "Zig-zag" traversal. Count the number of times where you need to flip the "leftToRight" flag.

answered Aug 14, 2012 at 7:13

louis.luo

2,9814 gold badges32 silver badges47 bronze badges

Collectives™ on Stack Overflow

Non recursive Program to find minimum height of Binary tree

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related