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.

Induction

Recursion has to be the easiest way to do this, what's the reason you want to avoid it? – Nanette

Is the depth field the distance from root, or from the farthest child? – Vivian

Kirschstein: There are reasons to avoid recursive calls on platforms with limited resources (e.g. embedded systems). A non recursive algorithm with a constant memory foot print is often necessary. – Allpurpose

The recursion posts I've read on SO give the advice that recursion should be used for a max of 10 levels. 10 levels in a complete tree is 1024 items so I'm curious how you'd do it for more than that (which I assume other trees based on the Binary Tree would use, albeit always balanced) – Induction

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

    }

}

Penicillin

I'm after setting the depths too – Induction

+1 for the answer. There has to be a better way to get the depth without requiring each node to have a Depth property though, right? – Engineering

@RepoMan yes. You can change the recursive function to function int getDepth (Node head, string val, int depth). Pass in depth+1 to the recursive calls. – Penicillin

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.

Harappa

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

Trapper

Answer 4

Here is the most efficient solution I've come up with (C++). The trick is to use a second queue to store the children of all nodes at your current level. This will work for balanced and unbalanced binary trees.

template <class T>
struct TreeNode {
  TreeNode<T>* left_;
  TreeNode<T>* right_;
  T* data_;
};

template <class T>
int find_depth( const TreeNode<T>* root ) {   
  if ( root == NULL ) return 0;
  int depth = 0;
  std::queue<const TreeNode<T>*>* q1 = new std::queue<const TreeNode<T>*>;
  std::queue<const TreeNode<T>*>* q2 = new std::queue<const TreeNode<T>*>;
  q1->push( root );
  while ( !q1->empty() ) {
    // At the top of the outer loop q1 contains a complete horizontal level of the tree                                                                                  
    depth++;

    // Swap the queue pointers to avoid any deep copies                                                                                                                  
    std::queue<const TreeNode<T>*>* tmpQ = q2;
    q2 = q1;
    q1 = tmpQ;

    // Iterate over this level, inserting all children into q1                                                                                                           
    while( !q2->empty() ) {
      const TreeNode<T>* node = q2->front();
      if ( node->left_ != NULL ) q1->push( node->left_ );
      if ( node->right_ != NULL ) q1->push( node->right_ );
      q2->pop();
    }
  }
  delete q1;
  delete q2;
  return depth;
}

Roan