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), getDepth(head.Right);
}

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);
      }
     }

    }

}

Answer 2

I assume you mean filling in the Depth value on node, and/or finding max depth. One way to do this would be using two lists, and doing the level order as suggested. It'd be akin to:

int level=0;
List<Node> currentLevel = new List<Node>{root};
while(currentLevel.Count != 0)
{
  List<Node> nextLevel = new List<Node>{};
  foreach(Node node in currentLevel)
  {
    if(node.Right!=null) nextLevel.Add(node.Right);
    if(node.Left != null) nextLevel.Add(node.Left);
    node.Depth=level;
  }
  level++;
  currentLevel=nextLevel;
}

Basically, you enumerate each node on a given level, then find each node on the next level; until you run out of nodes/levels. Clearly, List could be replaced with just about any list like data structure (Linked List, Queue, etc). And the last value of 'level' would be max depth + 1. I suspect.

One other clarification based on re reading of the question; if you are searching for a node with a specific value, and want to find its depth, you would change the foreach loop to include 'if(node.Value==searchValue) return level;'. And, technically, if you are searching for a specific value, you shouldn't be doing a Level Order Traversal, but rather a search for the value using relevant Binary Tree properties (e.g. val < currentNode.Value goto left else goto right), and tracking your depth. If you are given only the Node and want to find its depth, you would either need to perform a binary search for the node from root, or you would need to track the Node's parent.

Answer 3

Here's a simpler solution, I think. If the data structure allowed for an arbitrary number of children, this solution could be easily modified for that case too:

int getDepthNoRecursion(Node n) {
  if(n == null) {
    return 0;
  }
  int retval = 0;
  n.depth = 1;
  Stack s = new Stack();
  s.push(n);
  while(!s.isEmpty()) {
    Node n = (Node) s.pop();
    int currDepth = n.depth;
    if(currDepth > retval) {
      retval = currDepth;
    }
    if(n.left != null) {
      n.left.depth = currDepth + 1;
      s.push(n.left);
    }
    if(n.right != null) {
      n.right.depth = currDepth + 1;
      s.push(n.right);
    }
  }
  return retval;
}
class Node {
  Node left;
  Node right;
  int depth = 0;
}