stack overflow binary search tree calculating depth

Question

I'm trying to calculate the depth of a key in a binary search tree and I am getting a stack overflow error and I'm not sure why. Here is my current code.

private int calcDepth( Tree<K, V> x, K keyIn, int currentLevel){ 
  //BASE CASE  
  if (this.key.compareTo(keyIn) == 0) return currentLevel; 

  if (this.key.compareTo(keyIn) < 0){ 
     return calcDepth(this.left, keyIn, currentLevel+1);  
  }

  if (this.key.compareTo(keyIn) > 0){ 
     return calcDepth(this.right, keyIn, currentLevel + 1); 
  }

  return -1; 
}

and this is my algorithm

//ALGORITHIM 
//1. if the current key is equal to the parameter key 
//   return the currentLevel 
//2. if the current key is less than the parameter key 
//   go left and increment the level 
//3. if the current key is greater than the paramete key 
//   go right  and increment the level 
//4. if none of these cases are met (key is not in tree
//   return -1

I am new to java so forgive the beginner level of the question

The algorithm fails to return -1 if the given key is not present — fps

Ousmane D. Ousmane D. · Accepted Answer · 2017-04-10T17:38:57

I am getting a stack overflow error and I'm not sure why

this is due to the fact that, you're always passing this.left and this.right as the argument to the method calcDepth which is always the same. Also, this.key is always the same, so essentially you're always comparing two keys (this.key and keyIn) without actually traversing down the tree. i.e it should be:

if (x.key.compareTo(keyIn) == 0)

then when you invoke:

calcDepth(x.left, keyIn, currentLevel+1);

or

calcDepth(x.right, keyIn, currentLevel + 1);

x is a different instance at each invocation of the method.

It seems that you're not doing anything with the parameter x.You're supposed to use x.key (where x denotes the current instance of the tree).

Now x.left and x.right will be different at each invocation of the method, so essentially we're narrowing down the problem and reaching towards the base case, hence the method will be able to wind back to the calling methods and eventually end without a StackOverflow Exception.

Lastly but not least, there is an additional error within your code, the algorithm fails to return -1 if the given key is not present. To overcome this problem simply insert a condition that will check if the current tree is null if that's the case we didn't find our key and we can simply return -1.

note - this will also prevent the possibility of NullPointerException.

private int calcDepth( Tree<K, V> x, K keyIn, int currentLevel){ 

  if(x == null) return -1; // key doesnt exist if this is true

  if (x.key.compareTo(keyIn) == 0) return currentLevel;  //BASE CASE  

  if (x.key.compareTo(keyIn) < 0){   // check left tree
      return calcDepth(x.left, keyIn, currentLevel+1);  
  }

  if (x.key.compareTo(keyIn) > 0){  // check right tree
      return calcDepth(x.right, keyIn, currentLevel + 1); 
  }

  return -1; 
}

stack overflow binary search tree calculating depth

1 Answers