Get actual index during insertion in a BST
<p>I want to create a BST, which on insertion of element will return the index of it in a perfectly balanced tree. For example (the number in parenthesis indicates actual index) : </p>

<pre><code>  5(1)
    / \
   /   \
  3(2)  6(3)
 /
2(4)
</code></pre>

<p>or </p>

<pre><code>1(1)
 \
  \
   2(3)
    \
     \
      3(7)
</code></pre>

<p>In the second example, we can see that there is no left child of element 1, but still element 2 has an index of 3, as that would be the case in a perfectly balanced tree.</p>

<p>The root node starts with 1. </p>

<p>What would be an efficient way to return the index on insertion?</p>

<p>Now in insertion of an element in a BST my code is as follows:</p>

<pre><code>Node newNode = new Node(id);
if(root==null){
            root = newNode;
            return 1;
        }

Node current = root;
        Node parent = null;
        while(true){
            parent = current;
            if(id&lt;current.data){                
                current = current.left;
                if(current==null){
                    parent.left = newNode;
                    return;
                }
            }else{

                current = current.right;
                if(current==null){
                    parent.right = newNode;
                    return;
                }
            }
        }
</code></pre>

<p>I am not able to understand how I should maintain which level the element is being inserted in to calculate the index. </p>

<p>The number of elements which can be inserted is at max 3*10^5. Storing in an array to get the indexes wont be an effective method </p>