Recursively find depth of a node in a binary tree

Question

I'm stuck with a recursive function to find the depth of a node in a binary tree, more specifically in the else condition:

If the tree was a binary search tree, knowing that the left child value is always lower than the parent one and that the right child is always higher, I could add an if condition so that if the node x value is inferior to the root I always return with root->leftchild and viceversa, but because the tree is not a binary search one I have to check both left and right and I'm stuck with two consecutive return in the else condition.

When looking at the function, assume that the node always exist,that the node x is never the root and the passed depth at the beginning is always 0.

int node_depth (Node x,Node root,int depth){
   if(x->parent==root){
       return depth;
   }
   else{
       return node_depth(x,root->leftchild,depth+1);
       return node_depth(x,root->rightchild,depth+1);
   }
}

If tree was binary search:

else{
        if(x->value<root->value){
           return node_depth(x,root->leftchild,depth+1);
        }
        if(x->value>root->value){
           return node_depth(x,root->rightchild,depth+1);
        }
    }

Note that only the first of the two `return` statements in the `else` branch will be executed; the keyword `return` specifically means "stop execution of this function here". — Stef, Dec 02 '20 at 12:31
You don't need recursion at all here. Just iterate up until you get to root, something like `int depth = 0; while (x != root) {depth++; x = x->parent;}` — Jabberwocky, Dec 02 '20 at 12:31
You you please define what exactly you mean by "depth", possibly by showing an example with a picture. — Jabberwocky, Dec 02 '20 at 12:36
Please show us the struct example, if you are storing the parent of every node it makes you job a lot easier — ACoelho, Dec 02 '20 at 12:37
@Stef that's what I'm stuck at, I have to check both left and right but I don't know what if condition to put to know which one of the two returns get executed — Spyromancer, Dec 02 '20 at 12:38
@ACoelho struct has the int value, the pointer to parent, to left child and to right child — Spyromancer, Dec 02 '20 at 12:38
@Jabberwocky depth as intended in the first answer of this post https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height — Spyromancer, Dec 02 '20 at 12:40
@Mizzet then the solution is in my first comment. Do you really want to do this recursively? (Which would be pretty pointless in your case because you store the parent node). — Jabberwocky, Dec 02 '20 at 12:44

ACoelho · Accepted Answer · 2020-12-02T12:42:45.430

0

You need to find the maximum depth of any given node x from the root:

int node_depth(Node x, int depth){
    if (!x->parent) return depth;
    return node_depth(x->parent, depth + 1); 
}

You just go 'up' the tree until you find that the parent does not exists (meaning x is the root,)

edited Dec 02 '20 at 12:42

answered Dec 02 '20 at 12:31

ACoelho

341
1
11

I'm not sure he wants that. Your function return the "downwards" depth of a node, but I think he wants the depth of the node itself from the root. – Jabberwocky Dec 02 '20 at 12:34

Recursively find depth of a node in a binary tree

1 Answers1