Fog Creek Software
Discussion Board




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

*  Recent Topics

*  Fog Creek Home