BST to Linked-list


Write a function to convert BST(Binary Search Tree) to a doubly Linked list.

Possible Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct node
{
  int data;
  struct node *l;
  struct node *r;
};
 
typedef node Node;
 
void BST2DLL( Node * root, Node * first, Node * last)
{
  if( !root)  return;
  if(root->l)   BST2DLL(root->l, first, root);
  else
  {
    root->l = first;
    if(first)  first->r = root;
  }
  if(root->r)   BST2DLL(root->r, root, last);
  else
  {
    root->r = last;
    if(last)   last->l = root;
  }
}
The above function requires 2 Nodes ‘first’ and ‘last’ already existing acting as head and tail nodes. In case you don’t want to use them (preserve space) just pass NULL as BST2DLL(root, NULL, NULL)
At the end if you have passed non-null value for first, then first remains as the header node. Else(passed as NULL), root is the starting node for the DLL.

0 comments:

Post a Comment