title: Binary search tree compute the coordinate of nodes
body: <p>I need to get the x,y coords of all nodes, for example: </p>
  
  <pre><code>        10
     8        15
  7    9     13
  </code></pre>
  
  <p>X: the number of nodes visited already before visiting the node with in-order traversal</p>
  
  <p>Y: the depth of the node from the root</p>
  
  <p>e.g. for node 15, x=5 (before 15: already visited 7, 8, 9, 10, 13), y=1(second level)</p>
  
  <p>There is no parent pointer for the tree</p>
  
  <pre><code>int inorder(Node *node, int x) {
  
      if (node-&gt;left)
          x = inorder(node-&gt;left, x);
      x++;
      if (node-&gt;right)
          inorder(node-&gt;right, x);
      return x;
  }
  
  
  
  int x0(Node *node) {
      return inorder(node, -1);
  }
  
  
  
  int findY(Node *node, Node *from) {
  
      if (node == from)
          return 0;
      else if (node-&gt;item &lt; from-&gt;item)
          return findY(node, from-&gt;left) + 1;
      else
          return findY(node, from-&gt;right) + 1;
  }
  
  int y0(Node *node) {
      return findY(node, theRoot);
  }
  </code></pre>
  
  <p>result: x is wrong and y is correct</p>
  
  <p>print: </p>
  
  <pre><code>void printCoord() {
  
      queue&lt;Node*&gt; q;
      q.push(theRoot);
  
  
      int curLevel = 0;
      while (q.size() &gt; 0) {
          Node *n = q.front();
          q.pop();
  
          int x = x0(n);
          int y = y0(n);
  
          if (y &gt; curLevel) {
              curLevel = y;
              cout &lt;&lt; endl;
          }
  
          cout &lt;&lt; n-&gt;item &lt;&lt; "(" &lt;&lt; x &lt;&lt; "," &lt;&lt; y &lt;&lt;")";
          if (n-&gt;left)
              q.push(n-&gt;left);
          if (n-&gt;right)
              q.push(n-&gt;right);
      }
  
  }
  
  
  
  
  
  
  
  AvlTree tree;
  tree.insertBalance(10);
  tree.insertBalance(8);
  tree.insertBalance(15);
  tree.insertBalance(7);
  tree.insertBalance(9);
  tree.insertBalance(13);
  
  
  tree.printCoord();
  </code></pre>
  
  <p>Result: </p>
  
  <pre><code>10(2,0)
  8(1,1)15(1,1)
  7(0,2)9(0,2)13(0,2)
  </code></pre>
  
  <p>I have tried (which I don't think is correct because the right subtree traversal is not counted for the node)</p>
  
  <pre><code>int inorder(Node *node, int x) {
  
      if (node-&gt;left)
          x = inorder(node-&gt;left, x);
      x++;
      if (node-&gt;right)
          x = inorder(node-&gt;right, x);
      return x;
  }
  </code></pre>
  
  <p>and the result is </p>
  
  <pre><code>10(5,0)
  8(2,1)15(1,1)
  7(0,2)9(0,2)13(0,2)
  </code></pre>