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

[I like Serena]

Do we have to use a new variable $k$ or could we also do it in an other way? (Thinking)

What do you want to use [m]k[/m] for? (Wondering)
Its name doesn't say anything about its purpose, and as it is currently used, it doesn't seem to do anything useful.

 

[evinda]

What do you want to use [m]k[/m] for? (Wondering)
Its name doesn't say anything about its purpose, and as it is currently used, it doesn't seem to do anything useful.

How could we compare the depth of the first leaf with the depth of the second one?

 

[I like Serena]

How could we compare the depth of the first leaf with the depth of the second one?

I'm thinking with something like this:

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

(Wasntme)

 

[evinda]

I'm thinking with something like this:

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

(Wasntme)

Applying the above algorithm at this tree :

View attachment 3594

I got the following:

currentDepth=0
treeDepth=0
traverseTree(a)
currentDepth=1
result=traverse(b)
currentDepth=2
result=traverseTree(e)
currentDepth=3
result=traverseTreef)
currentDepth=4
result=traverse(h)
currentDepth=5
result=traverseTree(i)
currentDepth=6
result=TraverseTree(NULL)
treeDepth=6

But, then result doesn't get any value.. (Worried)
At the case when [m]treeDepth=0[/m], do we have to return success? (Thinking)

 

[I like Serena]

At the case when [m]treeDepth=0[/m], do we have to return success? (Thinking)

Well spotted! I forgot that one. (Blush)

 

[evinda]

Well spotted! I forgot that one. (Blush)

So, if we want to trace the algorithm, I tried the following:

View attachment 3605

Is it right? If so, how could we continue? (Sweating)

 

[I like Serena]

So, if we want to trace the algorithm, I tried the following:

View attachment 3605

Is it right? If so, how could we continue? (Sweating)

That looks right, although I think the success should be at depth 6.
At that point, we store the currentDepth in treeDepth.
And then we go back up, and then down into the next child.
Or rather, we keep backing up, until we can go down again. (Wasntme)

 

[evinda]

That looks right, although I think the success should be at depth 6.
At that point, we store the currentDepth in treeDepth.
And then we go back up, and then down into the next child.
Or rather, we keep backing up, until we can go down again. (Wasntme)

So, are these commands executed then?

[m] currentDepth++; [/m]

and

[m] result=traverseTree(c) [/m]

Or am I wrong?

Doesn't [m]currentDepth[/m] count the sum of the depths of the leaves? (Thinking)

 

[I like Serena]

So, are these commands executed then?

[m] currentDepth++; [/m]

and

[m] result=traverseTree(c) [/m]

Or am I wrong?

I don't understand your question.
Perhaps I'm missing the context. (Thinking)

Doesn't [m]currentDepth[/m] count the sum of the depths of the leaves? (Thinking)

The variable [m]currentDepth[/m] is supposed to track the current depth of any node in the tree.
If it does anything else, there is a mistake in the program.
So no, I don't think it counts the sum of the depths of the leaves. (Nerd)

 

[evinda]

The variable [m]currentDepth[/m] is supposed to track the current depth of any node in the tree.
If it does anything else, there is a mistake in the program.
So no, I don't think it counts the sum of the depths of the leaves. (Nerd)

Do we have to declare then maybe the variable [m]currentDepth[/m] inside the algorithm and not outside? (Thinking)

 

[I like Serena]

Do we have to declare then maybe the variable [m]currentDepth[/m] inside the algorithm and not outside? (Thinking)

That would be better from the perspective of good programming practice. (Smile)
It does mean that it should be passed as a parameter to the recursive function. (Thinking)

 

[evinda]

That would be better from the perspective of good programming practice. (Smile)
It does mean that it should be passed as a parameter to the recursive function. (Thinking)

I meant something else... (Shake)

When we declare [m] currentDepth [/m] as a global variable, it will increase at the whole function, independent from the node we are looking at in order to check if it is a leaf.

So, it won't track the current depth of any node in the tree, but the sum of depths..

Or am I wrong? (Worried)

 

[I like Serena]

I meant something else... (Shake)

When we declare [m] currentDepth [/m] as a global variable, it will increase at the whole function, independent from the node we are looking at in order to check if it is a leaf.

So, it won't track the current depth of any node in the tree, but the sum of depths..

Or am I wrong? (Worried)

It will track the current depth, if we increment it whenever we make a recursive call, and decrement it right after that call returns. (Nerd)

 

[evinda]

It will track the current depth, if we increment it whenever we make a recursive call, and decrement it right after that call returns. (Nerd)

Oh yes, you are right! (Nod)

At the beginning, we get that [m]TreeDepth=6[/m], but shouldn't it be [m]TreeDepth=5[/m] ? Or am I wrong? (Thinking)

Also, when we execute [m] traverse(j) [/m] and look at the child [m] k [/m] of [m]j[/m], the command [m] return failure; [/m] is executed.
Does this mean that the algorithm terminates and we don't look at the other child of [m] j [/m] and also we don't go back to the recursive calls? (Thinking)

 

[I like Serena]

Oh yes, you are right! (Nod)

At the beginning, we get that [m]TreeDepth=6[/m], but shouldn't it be [m]TreeDepth=5[/m] ? Or am I wrong? (Thinking)

Also, when we execute [m] traverse(j) [/m] and look at the child [m] k [/m] of [m]j[/m], the command [m] return failure; [/m] is executed.
Does this mean that the algorithm terminates and we don't look at the other child of [m] j [/m] and also we don't go back to the recursive calls? (Thinking)

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

What is the context? (Wondering)

 

[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)