Finding Depth & Height of Node w/ Key $r$ in $\text{AVL tree}$

[evinda]

Hi! (Wave)

We have an $\text{AVL tree}$ and we are given a key $r$. I want to write an algorithm that finds the depth and height of the node, of which the key is $r$.

So, do we have to compare the key of the root with the key $r$ and if it is greater we will have to continue at the left subtree to find the element with the key $r$ and if it is smaller we will look at the right subtree?
If the root has the key $r$, the depth will be equal to $0$, right? How could we then find the height? (Thinking)

 

[I like Serena]

Hi! (Wave)

Hey! (Smirk)

We have an $\text{AVL tree}$ and we are given a key $r$. I want to write an algorithm that finds the depth and height of the node, of which the key is $r$.

So, do we have to compare the key of the root with the key $r$ and if it is greater we will have to continue at the left subtree to find the element with the key $r$ and if it is smaller we will look at the right subtree?

Yep! (Smile)

If the root has the key $r$, the depth will be equal to $0$, right? How could we then find the height? (Thinking)

Recursively iterate through the remainder of the tree down and track what the maximum is that you go down? (Wondering)

 

[evinda]

depth=0;
Algorithm(pointer R,r){
  if (R->key==r){
     return depth;
  }
  else if (R->key<r){
      depth++;
      Algorithm(R->RC,r)
      depth--;
  }
  else {
      depth++;
      Algorithm(R->LC,r)
     depth--;
    }
}

Can we find like that the depth of the node with key $r$ ? (Thinking)

If so, suppose that we have this tree:

View attachment 3633

Then, these commands will be executed, right? (Thinking)

depth=0
Algorithm(A,64)
depth=1
Algorithm(C,64)
depth=2
Algorithm(F,64)
return depth
After this command is executed: [m] return depth; [/m], will the algorithm terminate? (Thinking)

 

[I like Serena]

Can we find like that the depth of the node with key $r$ ? (Thinking)

Yes. (Smile)

After this command is executed: [m] return depth; [/m], will the algorithm terminate? (Thinking)

Not immediately. (Thinking)

It will return to the previous recursion level, where the return value is ignored.
Then depth gets decremented.
And since there is no return statement at the end of the function, nothing will get returned.

After returning from all recursion levels, the depth will be 0 again, and nothing will have been returned. (Worried)

 

[evinda]

Not immediately. (Thinking)

It will return to the previous recursion level, where the return value is ignored.
Then depth gets decremented.
And since there is no return statement at the end of the function, nothing will get returned.

After returning from all recursion levels, the depth will be 0 again, and nothing will have been returned. (Worried)

So should it be maybe like that? (Thinking)

depth=0;
Algorithm(pointer R,r){
  int k;
  if (R->key==r){
     return depth;
  }
  else if (R->key<r){
      depth++;
      k=Algorithm(R->RC,r)
      depth--;
  }
  else {
      depth++;
      k=Algorithm(R->LC,r)
      depth--;
   }
   return k;
}

 

[I like Serena]

So should it be maybe like that? (Thinking)

depth=0;
Algorithm(pointer R,r){
  int k;
  if (R->key==r){
     return depth;
  }
  else if (R->key<r){
      depth++;
      k=Algorithm(R->RC,r)
      depth--;
  }
  else {
      depth++;
      k=Algorithm(R->LC,r)
      depth--;
   }
   return k;
}

Yes. That should work to find $r$ and to return its depth. (Smile)

However, what wil happen if $r$ is not present in the tree? (Worried)

 

[evinda]

Yes. That should work to find $r$ and to return its depth. (Smile)

However, what wil happen if $r$ is not present in the tree? (Worried)

So, do we have to have also a variable that gets the value $1$ if we found such a node? (Thinking)

Also, do we have to use now the depth in order to find the height? (Thinking)

 

[I like Serena]

So, do we have to have also a variable that gets the value $1$ if we found such a node? (Thinking)

Also, do we have to use now the depth in order to find the height? (Thinking)

Your algorithm should run through 2 phases:

1. Find the node $r$ and record its depth.
2. Recursively visit all children of the node with $r$ and record the maximum depth.

The height is the difference between the 2. (Nerd)Btw, you also need to make sure the algorithm behaves if $r$ cannot be found.
As it is now, it will crash!

 

[evinda]

Your algorithm should run through 2 phases:

1. Find the node $r$ and record its depth.
2. Recursively visit all children of the node with $r$ and record the maximum depth.

The height is the difference between the 2. (Nerd)

But, won't the depth of the children of the node with $r$ be always $0$ or $1$, since it is one level after this node?

Or have I understood it wrong? (Worried)

 

[I like Serena]

But, won't the depth of the children of the node with $r$ be always $0$ or $1$, since it is one level after this node?

Or have I understood it wrong? (Worried)

How so? (Wondering)

Let's take a look at your example tree.
It has $50$ in its root.
Suppose we want to find $r=50$.
Then its depth is $0$, while its height is $2$. (Thinking)

 

[evinda]

How so? (Wondering)

Let's take a look at your example tree.
It has $50$ in its root.
Suppose we want to find $r=50$.
Then its depth is $0$, while its height is $2$. (Thinking)

https://www.physicsforums.com/attachments/3634

If we want to find the depth and height of the node with key 100, we will see that $d=1$, right?
The children of this node are D and E.
Isn't their depth equal to $d+1$? (Sweating)

 

[I like Serena]

https://www.physicsforums.com/attachments/3634

If we want to find the depth and height of the node with key 100, we will see that $d=1$, right?
The children of this node are D and E.
Isn't their depth equal to $d+1$? (Sweating)

The deepest child starting from the node with key 100 is node F.
That means that the height of node 100 is 2. (Wasntme)

See for instance: algorithm - What is the difference between tree depth and height? - Stack Overflow

 

[evinda]

Your algorithm should run through 2 phases:

1. Find the node $r$ and record its depth.
2. Recursively visit all children of the node with $r$ and record the maximum depth.

The height is the difference between the 2. (Nerd)

Do we have to find the height inside the function [m] Algorithm [/m] ?

Also, do we have to find again, after having found the depth, the position at which we found the node with key $r$ ? (Thinking)

Btw, you also need to make sure the algorithm behaves if $r$ cannot be found.
As it is now, it will crash!

So, do we have to consider a variable [m] found [/m] like that? (Thinking)

depth=0;
Algorithm(pointer R,r){
  int k,found=0;
  if (R->key==r){
     found=1;
     return depth;
  }
  else if (R->key<r){
      depth++;
      k=Algorithm(R->RC,r)
      depth--;
  }
  else {
      depth++;
      k=Algorithm(R->LC,r)
      depth--;
   }
   return k;
}

 

[I like Serena]

Do we have to find the height inside the function [m] Algorithm [/m] ?

Up to you. (Wait)

Also, do we have to find again, after having found the depth, the position at which we found the node with key $r$ ? (Thinking)

I believe that can be part of the same algorithm.
No need to "find again". Just continue to recurse differently after we have found $r$. (Thinking)

So, do we have to consider a variable [m] found [/m] like that? (Thinking)

I don't think so.
The point is that you cannot refer to [m]R->key[/m] as long as you cannot be sure the R != NULL.
You need a check whether R == NULL or not! (Doh)

 

[evinda]

I believe that can be part of the same algorithm.
No need to "find again". Just continue to recurse differently after we have found $r$. (Thinking)

Could you give me a hint how we could do this? (Worried)

I don't think so.
The point is that you cannot refer to [m]R->key[/m] as long as you cannot be sure the R != NULL.
You need a check whether R == NULL or not! (Doh)

A ok... (Thinking)

 

[I like Serena]

Could you give me a hint how we could do this? (Worried)

Let's see...

I would set it up with something like:

Algorithm(root, r, *depth, *height)
  node = Find key(root, r, depth)
  if node != NULL
    *height = Determine height(node, 0)

Find key(R, r, *depth)
  Search the tree for r
  if found
    register its depth in *depth
    return its node
  else
    return NULL

Determine height(R, depth)
  if R == NULL
    return depth - 1
  leftHeight = Determine height(R->left, depth + 1)
  rightHeight = Determine height(R->right, depth + 1)
  return max(leftHeight, rightHeight)

(Wasntme)