CODEWITHSUNDEEP
calgorithmlistbinary-search-tree
Imposter
Imposter

Reputation: 2686

convert a binary search tree to doubly linklist using recursion

As mentioned in the Title , I have a Binary search tree. I want to convert it to sorted doubly linklist using recursion.

My code

 for each node in tree
   find max of left sub-tree and assign its right to present node ,present node left to max 
   find min of right sub-tree and assign its left to present node ,present node right to max 
   and now recursively do same thing to other nodes in BST .

but this solution is not efficient as it reaches each node more than one time .In my quest of optimized code i got a link from google greatTreeList sollution . I have searched the same in SO both sollutions are same and worked for me. I didnt understand the append function of the sollution as it contains code 

join(alast,b)
join(blast,a)

For tree whose nodes are inserted in following order 10,5,9,6,8,7,12,11,13,14

can anyone please explain how join(alast,b) join(blast,a)

are linking node in each recursion call.

Upvotes: 3

Views: 562

Answers (3)

Rusty Rob
Rusty Rob

Reputation: 17173

Expanding on Elemental's answer

Traverse(Node N)
  Traverse(N.left);
  Add N to the linked list
  Traverse(N.right);

To add N to the linked list,

your linked list class or data structure should have an append() method or similar.

Use your imagination, but something like this:

def append(N):
    new_tail = node(val=N, prev=self.tail, next=None)
    self.tail.next = new_tail
    self.tail = new_tail

of course you also need to add self.head = self.tail the first time you append.

Upvotes: 1

Elemental
Elemental

Reputation: 7521

I think you are over thinking this actually quite easy task - extracting the data from a binary tree in order is as simple as doing a depth first traversal - this is the point of a binary tree that it very efficiently gives you the elements in the sorted order.

So what you need to do is a standard depth first walk of the tree and each time you find a node add it to you linked list.

This in order depth first recursion is fairly straight forward is pseudocode:

Traverse(Node N)
  Traverse(N.left);
  Add N to the linked list
  Traverse(N.right);

I suggest you try this manually on you example so you see how it works.

Upvotes: 1

Philip
Philip

Reputation: 5917

In order to convert a binary search tree to a sorted doubly linked list, one typically performs an inorder depth-first traversal, building the list along the traversal.

Try to come up with code that performs an inorder depth-first traversal and prints the items of the binary tree in sorted order. From there, it should be easy to complete your task.

Upvotes: 1

Related Questions