java - Get position of a value in a BST's inorder list(without creating the list) -

i totally stuck on problem. need output position of value in inorder list (first index 0). caveat can't create list , search through it. each node have variable contains information how many nodes in given tree (including root). have working 50% of cases rest fail in hard understand ways... if value doesn't exist need return index have been.

in class tree

public int position(int val) {     if (this.isempty()){         return 0;     }      if (val == root.key){         return (root.subnodes - root.rightchild.subnodes) - 1;     }      if (val < root.key){         return root.position(0,root.subnodes - 1,val,root);     } else {         return (root.subnodes - root.rightchild.subnodes) +root.position(0,root.subnodes - 1,val,root.rightchild);     }  } 

in class node

int position(int min, int max, int k, node n){     if (k == n.key){         if (n.rightchild != null){             return n.subnodes - (n.rightchild.subnodes);         }         return max;     }     if (n.rightchild == null && n.leftchild == null){         return 1;     }     if (k < n.key){         return position(min ,n.leftchild.subnodes - 1, k, n.leftchild);     }      if (k > n.key && n.rightchild != null){         return position(n.subnodes - (n.rightchild.subnodes + 1), n.subnodes - 1, k, n.rightchild);     }      return max; } 

the idea:

you can in order traversal of tree , keep track of number of nodes have visited. requires counter of sort , helper method.

we stop searching when find node value greater or equal desired value. because either found index of desired value or index of desired value go (the desired value wouldn't go in earlier or later indexes). if never find node equal or greater desired value, desired value go @ end of tree, has position equal count of nodes.

the implementation:

imagine have node

public class node {    int value;    node leftchild;    node rightchild;     // getters , setters } 

and tree

public class tree {     node root;     // getters , setters } 

inside of tree

public int position(int val) {    positionhelper(val, root, 0); }  public int positionhelper(int val, node currentnode, int steps) {    // in-order search checks left node, current node, right node    if(currentnode.getleftchild() != null) {        steps = positionhelper(val, currentnode.getleftchild(), steps++);    }     // found node or have moved on node, return current steps    if(currentnode.getvalue() >= val) {        return steps;    }     // next node index      steps++;     if(currentnode.getrightchild() != null) {        steps = positionhelper(val, currentnode.getrightchild(), steps++);    }     return steps; } 

let me know if has issues or there questions