Tree To Doubly Linklist a real good problem asked in my trilogy interview lets say we have a binary search tree and we are given the pointer to the root node e.g.                             (4)                           /      \                         /        \                       (2)      (5)                     /  \                     /    \                   (1)  (3) the structure used is struct tree{ int info; tree *left,*right; }; now write a recursive function that converts the tree into a circular doubly link list newroot (node 1)         \         \       |----------------------------------------------------------|       --->1  <>    2    <>    3    <>  4    <>    5<--         |-------------------------------------------------------| < - previous node > - next node use left pointer as previous use right pointer as next write a recursive function tree *treetolist(tree *node) which creates the circular link list and return the pointer to new root node to the caller function conditions no global variable to be used code as simple as it can be and list should be circular i.e. node 1 previous should be node 5 and node 5 next should be node 1 this one was a real good ques BondofUK Sunday, April 18, 2004 I am too lazy right now to write the detailed answer. Basically it is like inorder traversal. Yuo solve for the left subtree, then the right, and concatenate the two with the root in the middle. In each step, after concatenation, you make the root point to the leftmost node in the list. And finally, make the root and the last node in the right subtree point to each other. RJ Monday, April 19, 2004 tree* treetolist(tree *root) { if(root==NULL) return NULL; root->left=treetolist(root->left); root->right=treetolist(root->right); if(root->left==NULL)     root->left=root; if(root->right==NULL)     root->right=root; tree *lefts,*rights; lefts=root->left; root->left=root->left->left; rights=root->right->left; lefts->left=rights; rights->right=lefts; root->left->right=root; root->right->left=root; return lefts; } BondofUK Friday, April 23, 2004 This is a tough interview question. I'm still trying to verify that your solution is correct... MJ Thursday, July 08, 2004   Fog Creek Home