Tuesday, October 23, 2012

Binary Tree in cartesian plane

Assume that a binary tree is drawn over a Cartesian coordinate system (with X & Y axis) where the leftmost node is placed at point (0,0). So, we need to traverse the nodes and print in following manner:
For e.g., for this tree
a
b c
d e f g


Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0


Strategy:
You can easily note here that for any given node:
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...

int print(node* n, int &count) {
    if (!n) return -1;
    int height = print(n->left, count) + 1;
    printf("%d,%d,%d", n->data, count++, height);
    print(n->right, count);
    return height;
}
print(root, 0);

No comments:

Post a Comment