# Thread: Distance between root and leaf.

1. ## Distance between root and leaf.

Hi,
I wrote the following recursion for finding the distance between a root and a leaf, but am not quite sure how to make it work. Could anyone advise?
Code:
```int calc_depth(Node* tree, Node* zero)
{
if (!tree)
return 0;
if (zero->right || zero->left == tree)
return 1;
return (zero->right ? calc_depth(tree, zero->right) : calc_depth(tree, zero->left));
}```

2. What do you want to test in the line 5?

3. Silly me. Should have been:
Code:
```
int calc_depth(Node* tree, Node* zero)
{
if (!tree)
return 0;
if (zero->right == tree || zero->left == tree)
return 1;
return (zero->right ? calc_depth(tree, zero->right) : calc_depth(tree, zero->left));
}```

4. But it still would not work. Why is that?

5. The biggest problem is that you're not adding anything up. Think about it: the only thing that can possibly be returned from your function is 0 or 1, no matter how big the tree is.

And what is "zero"? Why are you comparing it to "tree"?

You should post your entire test program.

BTW, you haven't specified exactly what type of tree you're dealing with here. Obviously it's a binary tree, but is it arbitrary? complete? balanced?

6. also I do not understand in line 7 how you decide where the leaf will be in the right sub-tree or in the left sub-tree.

Looks to me you always go to the right if it exists, even if the leaf will be found on the left...

7. OK, is this better?:
Code:
```int calc_depth(Node* root, Node* leaf)
{
if (!root)
return 0;
return (leaf->right == root || leaf->left == root ? 1 : calc_depth(root, leaf->right) + calc_depth(root, leaf->left));
}```

8. But of course that would go through all the leaves, without actually determining the shortest path, wouldn't it?
PS It is the most general binary tree. Nothing else is specified.

9. looks like the result will be 1 if leaf is present in the tree and 0 otherwise

10. The leaf is certainly in the tree. Question is - what would be the shortest path to it.
Code:
```int calc_depth(Node* root, Node* leaf)
{
int depth = 0;
if (!root)
return 0;
return (leaf->right == root || leaf->left == root ? 1 : depth + calc_depth(root, leaf->right) + calc_depth(root, leaf->left));
}```
But again, even if that were to work, it would still not quite return the shortest distance, right?

11. You're digging down into the tree with the wrong input variable. Assuming that root is the top of the tree and leaf is the leaf you're looking for, then you need to search down with root->left and root->right. (If leaf is really a "leaf", then it's left and right pointers are NULL!)

12. Originally Posted by peripatein
The leaf is certainly in the tree. Question is - what would be the shortest path to it.
There is only one path from the root to the leaf (or indeed any node), otherwise the structure is not a tree. Hence, the question of what is the shortest path to it is trivial to answer: the path to the leaf is the shortest path.

Hence, to find the path, you would start from the root and search for the leaf, which is what oogabooga described in post #11.

13. Originally Posted by peripatein
Hi,
I wrote the following recursion for finding the distance between a root and a leaf, but am not quite sure how to make it work. Could anyone advise?
Code:
```int calc_depth(Node* tree, Node* zero)
{
if (!tree)
return 0;
if (zero->right || zero->left == tree)
return 1;
return (zero->right ? calc_depth(tree, zero->right) : calc_depth(tree, zero->left));
}```
Code:
```/*
calculate the depth of node node.
Tree has members right and left
*/
int calc_depth(Node *root, Node *node)
{
int ldepth, rddepth;

if(root == 0)
return 0;
if(root == node)
return 1;
ldepth = calc_depth(root->left, node);
rdepth = calc_depth(root->right, node);
if(ldepth)
return ldepth + 1;
if(rdepth)
return rdepth +1;

/* node not on this sub-branch */
return 0;
}```
This searches virtually the whole tree, so it's not the most efficient way of doing it. But it's easy.

14. This searches virtually the whole tree, so it's not the most efficient way of doing it.
If the tree has no structure besides being binary (as the OP has indicated), then there's no more efficient way than searching the whole tree.

And it's best not to just post a solution. Anyone here can do that.

15. actually it could be slightly optimized
Code:
```   ldepth = calc_depth(root->left, node);
if(ldepth)
return ldepth + 1;
rdepth = calc_depth(root->right, node);
if(rdepth)
return rdepth +1;```
no need to traverse right tree if already found on the left