bst to doubly linked list

// =========================================================
// 
//       Filename:  bst2list.cpp
// 
//    Description:  convert a bst to a linked list
// 
//        Version:  1.0
//        Created:  03/15/2012 10:21:02 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/15/2012, LI YAN
// 
// =========================================================

#include <cstdio>
using namespace std;

struct node {
    int val;
    node *left, *right; // for bst, it is lchild and rchild, for doubly linked list, it is prev and succ
};

node* bst2list(node *root)
{
    if (root==NULL) return NULL;

    node *subleft = bst2list(root->left);
    node *subright = bst2list(root->right);

    root->left = root->right = root;
    node *head, *tail, *ltail, *rtail;
    head=root;
    if (subleft) {
        ltail = subleft->left; tail=head->left;
        ltail->right = head; head->left = ltail;
        subleft->left = tail; tail->right = subleft;
        head = subleft;
    }
    if (subright) {
        tail=head->left; rtail = subright->left;
        tail->right = subright; subright->left = tail;
        head->left = rtail; rtail->right = head;
    }
    return head;
}

void print(node *root)
{
    if (root==NULL) return;
    print(root->left);
    printf(" %d", root->val);
    print(root->right);
}

void printlist(node *head)
{
    if (head==NULL) return;
    node *p=head;
    do {
        printf("%d ", p->val);
        p=p->right;
    } while (p!=head);
}

int main()
{
    node a[100];
    for(int i=0; i<10; ++i) {
        if (2*i+1<10) a[i].left=&a[2*i+1]; 
        else a[i].left = NULL;

        if (2*i+2<10) a[i].right=&a[2*i+2];
        else a[i].right = NULL;
    }
    // expected: true
    int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 280};
    // expected: false
    //int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 350}; 
    for(int i=0; i<10; ++i) {
        a[i].val = v[i];
    }

    node *root=&a[0];
    puts("input");
    print(root); putchar('\n');
    puts("convert to list");
    node *head=bst2list(root);
    printlist(head); putchar('\n');
}