Tuesday, March 15, 2011

Converting a Tree to a double Linked List

Q: Write a program which will accept Binary Search Tree and convert it to a sorted Double Linked List.

For example if the Binary search tree is as shown below…

tree

Then the converted doubly linked  list should be

list

Lets define the Node structure of the tree as follows

We can use recursive approach to solve this by just arranging the pointers..

Algorithm:

If tree is not empty

Convert Left Subtree to List and let hLeft point to it

Convert Right Subtree to List and left hRight point to it.

Append hLeft to root and then hRight

Working java Code:

No comments: