MHB Writing an Algorithm to Check Depth of Leaves in an Ordered Tree

[evinda]

I have lost the context, which is probably somewhere far back in this thread. (Blush)

What is the context? (Wondering)

We want to check if all the leaves of the ordered tree are at the same depth.

1.currentDepth=0;
2. treeDepth = 0;
3. traverseTree(node)
4.   if node = NULL
5.     if (treeDepth = 0) 
6.       treeDepth = currentDepth;
7.          return success
8.     else if (treeDepth != currentDepth)
9.          return failure
10.    else
11.    return success
12. for each child of node
13.    currentDepth++
14.    result = traverseTree(child)
15.    currentDepth--
16.    if result is failure
17.      return failure
18.  return success

I wanted to trace this algorithm for the tree of post #25.

At the beginning, we get that the depth of the tree is 6, but, actually it is 5, or not? Is this a problem? (Worried)

 

[I like Serena]

When we have, for example, this tree:

View attachment 3594

we call the functions [m]traverseTree(a,depth), traverseTree(b,depth+1), traverseTree(e,depth+2), traverseTree(f,depth+3), traverseTree(h,depth+4), traverseTree(i,depth+5)[/m], right? But.. what do we do after the command [m] return; [/m] , that is executed at the function [m]traverseTree(i,depth+5)[/m]? (Worried)

We want to check if all the leaves of the ordered tree are at the same depth.

At the beginning, we get that the depth of the tree is 6, but, actually it is 5, or not? Is this a problem? (Worried)

Isn't the number of edges between the root and the deepest leaf $6$? (Wondering)

 

[evinda]

Isn't the number of edges between the root and the deepest leaf $6$? (Wondering)

Oh, yes you are right... (Tmi)

But.. when [m] treeDepth [/m] gets the value [m] 6 [/m], we don't pass through the longest distance from the root to the deepest leaf, but we execute the following commands:

currentDepth=0
treeDepth = 0
traverseTree(a)
currentDepth=1
result=traverseTree(b)
currentDepth=2
result=traverseTree(e)
currentDepth=3
result=traverseTree(f)
currentDepth=4
result=traverseTree(h)
currentDepth=5
result=traverse(i)
currentDepth=6
result=traverseTree(NULL)
treeDepth=6
Or am I wrong? (Sweating)

 

[I like Serena]

Oh, yes you are right... (Tmi)

But.. when [m] treeDepth [/m] gets the value [m] 6 [/m], we don't pass through the longest distance from the root to the deepest leaf, but we execute the following commands:

currentDepth=0
treeDepth = 0
traverseTree(a)
currentDepth=1
result=traverseTree(b)
currentDepth=2
result=traverseTree(e)
currentDepth=3
result=traverseTree(f)
currentDepth=4
result=traverseTree(h)
currentDepth=5
result=traverse(i)
currentDepth=6
result=traverseTree(NULL)
treeDepth=6
Or am I wrong? (Sweating)

That is true.
This is the depth of the non-existing NULL child of $i$.
If it would exist, it would be at depth 6.
The deepest actually existing node in this sub tree is $i$ at depth $5$. (Wasntme)

 

[evinda]

That is true.
This is the depth of the non-existing NULL child of $i$.
If it would exist, it would be at depth 6.
The deepest actually existing node in this sub tree is $i$ at depth $5$. (Wasntme)

So, that what we find from a path that is not the longest one, doesn't correspond to the actual depth of the tree, right?
But, in our case it is indeed the right depth, that's why it didn't change, right? (Thinking)

 

[I like Serena]

So, that what we find from a path that is not the longest one, doesn't correspond to the actual depth of the tree, right?

Correct. (Smile)

But, in our case it is indeed the right depth

Yes. (Happy)

that's why it didn't change, right? (Thinking)

Huh?

 

[evinda]

Huh?

We found at the beginning [m]treeDepth=6[/m].. Couldn't it be that we find a greater value for [m]treeDepth[/m] or isn't it possible? (Thinking)

 

[I like Serena]

We found at the beginning [m]treeDepth=6[/m].. Couldn't it be that we find a greater value for [m]treeDepth[/m] or isn't it possible? (Thinking)

In the left sub tree we will find a maximum depth of 6, which is 1 more than the actual depth, since we find it at a NULL child.
When we recurse into the right sub tree we will reach a maximum depth of 7. (Wasntme)

 

[evinda]

In the left sub tree we will find a maximum depth of 6, which is 1 more than the actual depth, since we find it at a NULL child.
When we recurse into the right sub tree we will reach a maximum depth of 7. (Wasntme)

And does it matter or not, because of the fact that we just want to check if they are equal or not? (Thinking)

 

[I like Serena]

And does it matter or not, because of the fact that we just want to check if they are equal or not? (Thinking)

I'm not sure what you mean...

But yes, we only want to know of they are equal or not. (Nod)

 

[evinda]

I'm not sure what you mean...

I meant that that what we found isn't the actual depth, but the actual depth+1..
Or am I wrong? (Thinking)

 

[I like Serena]

I meant that that what we found isn't the actual depth, but the actual depth+1..
Or am I wrong? (Thinking)

That's why we always need to consider if anything should be plus or minus 1! (Rofl)

 

[evinda]

That's why we always need to consider if anything should be plus or minus 1! (Rofl)

(Bigsmile) (Wasntme) (Whew)

So, do we have to change something? (Thinking)

 

[I like Serena]

(Bigsmile) (Wasntme) (Whew)

So, do we have to change something? (Thinking)

What is it that you think might need to be changed? (Wondering)

 

[evinda]

What is it that you think might need to be changed? (Wondering)

Do we have to increment the depth, maybe, only when the child of the node we are looking at is not NULL? (Thinking)

 

[I like Serena]

Do we have to increment the depth, maybe, only when the child of the node we are looking at is not NULL? (Thinking)

It seems to me that makes the algorithm unnecessarily complicated.
Better would be to initialize depth to -1 instead of 0. (Thinking)

Note that if we execute the algorithm on a non-existent (NULL) tree, it should work consistently, meaning it should find a depth of -1. (Nerd)