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

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Properties
Click For Summary

Discussion Overview

The discussion revolves around finding the depth and height of a node with a specific key $r$ in an AVL tree. Participants explore algorithmic approaches to achieve this, including recursive strategies and considerations for handling cases where the key may not be present in the tree.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants propose comparing the key of the root with $r$ to navigate through the left or right subtree to find the node.
  • There is a suggestion that the depth of the node with key $r$ is $0$ if it is the root, but uncertainty exists about how to calculate the height.
  • One participant presents a recursive algorithm to find the depth, questioning whether it correctly returns the depth value.
  • Another participant points out that the algorithm may not return a value correctly due to the lack of a return statement at the end of the function.
  • There is a discussion about the need for a variable to indicate whether the node was found and how to handle cases where $r$ is not present in the tree.
  • Some participants suggest that the algorithm should run in two phases: first to find the node and record its depth, and second to calculate the height by visiting all children of the node.
  • Concerns are raised about whether the depth of the children of the node with $r$ would always be $0$ or $1$, leading to confusion about height calculations.
  • Participants discuss the necessity of checking for null pointers to avoid errors in the algorithm.

Areas of Agreement / Disagreement

Participants express multiple competing views on the algorithm's structure and functionality, particularly regarding how to handle cases where the key is not found and the calculation of height. The discussion remains unresolved with no consensus on the best approach.

Contextual Notes

There are limitations in the proposed algorithms, including missing checks for null pointers and the handling of cases where the key is absent from the tree. The discussion also reflects uncertainty about the definitions of depth and height in the context of the AVL tree.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Technology news on Phys.org
evinda said:
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)
 
Code: 
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)
 
evinda said:
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. :eek:
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)
 
I like Serena said:
Not immediately. (Thinking)

It will return to the previous recursion level, where the return value is ignored. :eek:
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)

Code: 
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;
}
 
evinda said:
So should it be maybe like that? (Thinking)

Code: 
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)
 
I like Serena said:
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)
 
evinda said:
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! :eek:
 
I like Serena said:
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? :confused:

Or have I understood it wrong? (Worried)
 
  • #10
evinda said:
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? :confused:

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)
 
  • #11
I like Serena said:
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)
 
  • #12
evinda said:
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
 
  • #13
I like Serena said:
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] ? :confused:

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 like Serena said:
Btw, you also need to make sure the algorithm behaves if $r$ cannot be found.
As it is now, it will crash! :eek:

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

Code: 
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;
}
 
  • #14
evinda said:
Do we have to find the height inside the function [m] Algorithm [/m] ? :confused:

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)
 
  • #15
I like Serena said:
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 like Serena said:
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)
 
  • #16
evinda said:
Could you give me a hint how we could do this? (Worried)

Let's see...

I would set it up with something like:
Code: 
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)
 

Similar threads

MHB Finding the $j^{th}$ Smallest Element in an AVL Tree
  • · Replies 7 ·
Replies
7
Views
2K
MHB Find Next Smallest & Greatest Key in BST
  • · Replies 1 ·
Replies
1
Views
2K
MHB Which node satisfies this property?
  • · Replies 20 ·
Replies
20
Views
4K
MHB Is my AVL-tree height finding method correct?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Understanding Heaps & Deleting Elements
  • · Replies 9 ·
Replies
9
Views
2K
MHB How do you draw a binary tree using pre-order and in-order traversal?
  • · Replies 14 ·
Replies
14
Views
3K
MHB Finding Depth of Perfect & Complete Binary Trees
  • · Replies 1 ·
Replies
1
Views
2K
MHB Union of Disjoint Sets with at Most k Sets - Algorithm
  • · Replies 2 ·
Replies
2
Views
2K
MHB How Can You Check if a Binary Tree Satisfies the Properties of a 2-3 Tree?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Divide Binary Search Tree at Key k: Algorithm & Analysis
  • · Replies 10 ·
Replies
10
Views
3K