Binary tree - find position in inorder traversal

Question

I have a binary search tree where i have to implement a method called

int valueAtPosition(int x) 

The problem is, that i need the position in an in order traversal.

To find the in order traversal i have this the following code, but i don't know how i count the recursive calls, to get the right position.

public void inOrderTraverseTree(Node root){
    if(root != null){
        inOrderTraverseTree(root.leftChild);
        System.out.println(root);
        inOrderTraverseTree(root.rightChild); 
    }    
}

Answer 1

You can also use a counter in the recursive approach. However, you can't simply pass an int counter argument - you need all calls to see the "same" counter, so you will have to wrap it in a class (or, as in this case, an inner class):

public static class Counter {
   private int value;
   public Counter(int initialValue) { value = initialValue; }
   public boolean decrement() { value--; return value == 0; }
   public boolean expired() { return value <= 0; }
}

public Node inOrderTraverseTree(Node root, Counter counter){
   if  (root != null && ! counter.expired()) {
       Node left = inOrderTraverseTree(root.leftChild, counter);
       if (left != null) {
            return left;
       } else if (counter.decrement()) {
            return root;
       } else {
            return inOrderTraverseTree(root.rightChild, counter); 
       }
   } else {
       return null;
   }
}

To find the 9th node in-order (using 1-based indexing), you would call this as

Node the9th = inOrderTraverseTree(root, new Counter(9));

If there is no 9th node, it would return null. If you want to use 0-based indexing instead, change { value--; return value == 0; } to { return value-- == 0; }