Retrieving a Binary-Tree node's depth non-recursively

Question

Can anyone point out a way of getting the depth of a Node in a Binary Tree (not a balanced one, or BST) without using recursion? Ideally in Java/C/C#

The node is represented as:

class Node
{
  Node Left;
  Node Right;
  string Value;
  int Depth;
}

Using Level Order with a FIFO list was my first thought, but I was stumped at detecting when the level changes, particular for unbalanced trees.

Answer 1

You can implement any resursive method with a stack, which is how resursion works anyways. Imagine your resursive function looks like

function int getDepth (Node head, string val)
{
    if (head == NULL)
        return -1;

    if (val == head.Value)
        return head.Depth;

    return MAX(getDepth(head.Left, val), getDepth(head.Right, val);
}

The non-resursive function looks something like

function int getDepth (Node head, string val)
{
    Stack s = new Stack();

    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (s.Value == val)
                return s.Depth;
            else
            {
                s.push(temp.Left);
                s.push(temp.Right);
            }
        }

    }


    return -1;
}

EDIT:

This function sets the depth for each node

function void setDepth (Node head)
{
    Stack s = new Stack();

    head.Depth = 0;
    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (temp.Left != NULL)
            {
                temp.Left.Depth = temp.Depth + 1;
                s.push(temp.Left);
            }

            if (temp.Right != NULL)
            {
                temp.Right.Depth = temp.Depth + 1;
                s.push(temp.Right);
            }
        }

    }

}