Binary search tree compute the coordinate of nodes

Question

I need to get the x,y coords of all nodes, for example:

        10
   8        15
7    9     13

X: the number of nodes visited already before visiting the node with in-order traversal

Y: the depth of the node from the root

e.g. for node 15, x=5 (before 15: already visited 7, 8, 9, 10, 13), y=1(second level)

There is no parent pointer for the tree

int inorder(Node *node, int x) {

    if (node->left)
        x = inorder(node->left, x);
    x++;
    if (node->right)
        inorder(node->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->item < from->item)
        return findY(node, from->left) + 1;
    else
        return findY(node, from->right) + 1;
}

int y0(Node *node) {
    return findY(node, theRoot);
}

result: x is wrong and y is correct

print:

void printCoord() {

    queue<Node*> q;
    q.push(theRoot);


    int curLevel = 0;
    while (q.size() > 0) {
        Node *n = q.front();
        q.pop();

        int x = x0(n);
        int y = y0(n);

        if (y > curLevel) {
            curLevel = y;
            cout << endl;
        }

        cout << n->item << "(" << x << "," << y <<")";
        if (n->left)
            q.push(n->left);
        if (n->right)
            q.push(n->right);
    }

}







AvlTree tree;
tree.insertBalance(10);
tree.insertBalance(8);
tree.insertBalance(15);
tree.insertBalance(7);
tree.insertBalance(9);
tree.insertBalance(13);


tree.printCoord();

Result:

10(2,0)
8(1,1)15(1,1)
7(0,2)9(0,2)13(0,2)

I have tried (which I don't think is correct because the right subtree traversal is not counted for the node)

int inorder(Node *node, int x) {

    if (node->left)
        x = inorder(node->left, x);
    x++;
    if (node->right)
        x = inorder(node->right, x);
    return x;
}

and the result is

10(5,0)
8(2,1)15(1,1)
7(0,2)9(0,2)13(0,2)

Answer 1

// your inorder function is not correct
bool inorder(Node* node, int* x, Node* root) {
    if (root==NULL)
        return false;

    if (inorder(node, x, root->left))
        return true;

    if (node==root) //inorder property here
        return true;

    (*x)++;

    if (inorder(node, x, root->right))
        return true;

    return false;

}

int x0(Node *node) {
    int x=0;
    if (inorder(node, &x, theRoot)) //you did't pass root here
        return x;
    else //not found
        return -1;

}

Points:

1. You didn't pass the root and checked with the query node. That's not correct. You need to search the tree from the root.
2. For any inorder property, basic idea is you go left, do what you want, then go right. But this may vary according to your problem.
3. If the query node is found, no further inorder call takes place. It returns all the way to x0 with x containing the desired value.

Answer 2

I'm pretty sure this:

if (node->right)
    inorder(node->right, x);

is supposed to be:

if (node->right)
    x = inorder(node->right, x);

Unless you really only mean to count the left-side nodes.