0

how to write a non-recursive java function that computes the depth of a node in a tree(not binary) given that node

 public int depth(Node node) {
    int depth = 0;
    while (node != root) {
       node =node.parent;
       depth++;
    }
    return depth;
}

this works for binary trees but what about if it is not binary

Luiggi Mendoza
  • 85,076
  • 16
  • 154
  • 332
Nada
  • 7
  • 1
  • 8
    This code will work for any __tree__ – Alex Shesterov Dec 15 '14 at 22:03
  • it's a tree. In a tree, a node has only one parent (as per definition of a tree), so it does not matter if the tree is binary or not. – njzk2 Dec 15 '14 at 22:04
  • Any recursive algorithm uses internal stack call and can be easily rewritten to non-recursive one. So, you could implement something like [this one](http://stackoverflow.com/a/5278667/2487403) but applied to your problem. – Everv0id Dec 15 '14 at 22:11
  • Any "rooted" tree. Any tree can be made "rooted" by designating one vertex as the root. Then the parent of vertex A is the unique vertex B, one step closer to the root. (From any vertex there is a unique path to the root.) – TravisJ Dec 15 '14 at 22:11
  • so the concept is the same, thank you very much for the clarification – Nada Dec 15 '14 at 22:14
  • You should ideally override hashCode() and equals() for the Node class and use that for comparison. – isak gilbert Dec 15 '14 at 22:54

0 Answers0