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

[evinda]

I don't understand your questions. (Doh)

The first time we get to the [m]return[/m], we need to register the depth.
Every other time, we need to check if the depth is the same as the one we previously registered. (Thinking)

I haven't undestood how we could do this, when we don't know how many leaves there are? (Worried)

 

[I like Serena]

I haven't undestood how we could do this, when we don't know how many leaves there are? (Worried)

For what would we need to know how many leaves there are? (Wondering)

When we traverse the tree, at some point we'll get to a leaf for the first time.
At that time, we can register its depth.
Then we continue traversing the tree.
Whenever we get to a leaf again, we'll check if its depth is the same as the one we registered before. (Thinking)

 

[evinda]

For what would we need to know how many leaves there are? (Wondering)

When we traverse the tree, at some point we'll get to a leaf for the first time.
At that time, we can register its depth.
Then we continue traversing the tree.
Whenever we get to a leaf again, we'll check if its depth is the same as the one we registered before. (Thinking)

Is it maybe like that? (Thinking)

depth=0;
traverseTree(node)
  int k;
  if node = NULL
    if (k!=depth) return failure
    return
  depth=0
  for each child of node
    depth++
    traverseTree(child)
  k=depth
  return success

Or am I wrong? (Thinking)

 

[I like Serena]

1. depth=0;
2. traverseTree(node)
3.   int k;
4.   if node = NULL
5.     if (k!=depth) return failure
6.     return
7.   depth=0
8.   for each child of node
9.     depth++
10.    traverseTree(child)
11.  k=depth
12.  return success

Isn't [m]k[/m] uninitialized when we get to line 5?
That would lead to chaos and madness. (Worried)Setting it to zero in line 7, would make it zero even if we've descended into the tree.
That can't be right! (Sweating)Line 9 is the only line where depth is incremented, and it is never decremented.
That should cause problems. (Doh)Line 11 is setting [m]k[/m], but after that it is never used... (Wasntme)

 

[evinda]

Isn't [m]k[/m] uninitialized when we get to line 5?
That would lead to chaos and madness. (Worried)Setting it to zero in line 7, would make it zero even if we've descended into the tree.
That can't be right! (Sweating)Line 9 is the only line where depth is incremented, and it is never decremented.
That should cause problems. (Doh)Line 11 is setting [m]k[/m], but after that it is never used... (Wasntme)

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

 

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