title: Java: Find the Depth of a Node not Found in a BST
body: <p>I have a binary search tree that stores in Strings, and I have been able to find the depths or heights of Strings that exist in the BST, but what I'm trying to do is find what the depth would be for a String that is not in the BST.</p>
  
  <p>Here is the algorithm that I'm using currently, which works perfectly to find the depth of a String that already exists in the BST:</p>
  
  <pre><code>public int getDepth(String data) {
      return getDepth(root, data, 1);
  }
  
  public int getDepth(Node root, String data, int level) {
      if (root == null)
          return 0;
  
      if (root.getData().getName().equals(data))
          return level;
  
      int ret = getDepth(root.leftChild, data, level + 1);
      if (ret != 0)
          return ret;
  
      ret = getDepth(root.rightChild, data, level + 1);
      return ret;
  
  }
  </code></pre>
  
  <p>My BST has the elements that were inserted in this order: "cat", "bird", "dog", "tiger", "elephant", "panda".</p>
  
  <p>So the binary tree should look like this:</p>
  
  <pre><code>                                   cat
                                    /   \
                                 bird   dog
                                           \
                                          tiger
                                         /     \
                                    elephant  panda
  </code></pre>
  
  <p>When I call the method on "dog" the output is: dog is at depth 2</p>
  
  <p>When I call the method on "hippo" the output is: hippo is at depth 0</p>
  
  <p>But the expected output of "hippo" should be: hippo is at depth 5</p>
  
  <p>Because hippo would be a child of elephant which is already in depth 4.</p>
  
  <p>Then for another case, what if I wanted to find the depth of "cow" that is not in the BST? It would have to be the left child of dog so the depth should be 3, however, I still get 0.</p>
  
  <p>So the question is without using a delete and/or restore method what case(s) do I need or what case(s) do I need to modify in the method above in order to determine the depth of a String not inside the BST?</p>