binary search tree - Java: Find the Depth of a Node not Found in a BST -

binary search tree - Java: Find the Depth of a Node not Found in a BST -

i have binary search tree stores in strings, , have been able find depths or heights of strings exist in bst, i'm trying find depth string not in bst.

here algorithm i'm using currently, works find depth of string exists in bst:

public int getdepth(string data) { homecoming getdepth(root, data, 1); } public int getdepth(node root, string data, int level) { if (root == null) homecoming 0; if (root.getdata().getname().equals(data)) homecoming level; int ret = getdepth(root.leftchild, data, level + 1); if (ret != 0) homecoming ret; ret = getdepth(root.rightchild, data, level + 1); homecoming ret; }

my bst has elements inserted in order: "cat", "bird", "dog", "tiger", "elephant", "panda".

so binary tree should this:

cat / \ bird dog \ tiger / \ elephant panda

when phone call method on "dog" output is: dog @ depth 2

when phone call method on "hippo" output is: hippo @ depth 0

but expected output of "hippo" should be: hippo @ depth 5

because hippo kid of elephant in depth 4.

then case, if wanted find depth of "cow" not in bst? have left kid of dog depth should 3, however, still 0.

so question without using delete and/or restore method case(s) need or case(s) need modify in method above in order determine depth of string not within bst?

try modified version of sec getdepth() method:

public int getdepth(node root, string data) { if (root == null || root.getdata().getname().equals(data)) { // nail spot - either below leaf // or matched node // if doing insert/replace, set info on spot homecoming 0; } if (issmallerthan(data, root.getdata().getname())) { homecoming 1 + getdepth(root.leftchild, data); } homecoming 1 + getdepth(root.rightchild, data); }

where issmallerthan(string a, string b) returns true if a smaller b. method depends on how want strings compared.

and don't need pass level along...

java binary-search-tree depth