# Convert Binary Tree Into Doubly Linked List

## Question

Convert binary search tree into doubly linked list. It’s required not to create any new node, but only turning pointers.

## Solution

The following shows the concept of this question.

``````8 / 6 0 -> 5 = 6 = 7 = 8 = 9 = 0 = 1 / / 5 7 9 1
``````

First, since node for both binary tree and doubly linked list have left and right node, they can use the same node structure. Then, looking the doubly linked list as a normal linked list, it is actually a in-order depth-first traversal result.

## Code

``````# node structure
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

# what to do with a node.
def visit(node):
global node_temp
global node_root
if not node_temp: node_root = node  # head
else: node_temp.right = node  # make right of temp to this
node.left = node_temp  # make temp to this left
node_temp = node  # next node

# bfs traversal
def depth_first_recursive_traversal_in_order(node):
if node is None: return
depth_first_recursive_traversal_in_order(node.left)
visit(node)
depth_first_recursive_traversal_in_order(node.right)

# a binary tree and display how was it before reflection
node_5 = Node(5)
node_7 = Node(7)
node_9 = Node(9)
node_1 = Node(1)
node_6 = Node(6, node_5, node_7)
node_0 = Node(0, node_9, node_1)
node_8 = Node(8, node_6, node_0)

# conversion
node_root = node_8
node_temp = None
depth_first_recursive_traversal_in_order(node_root)

# answer should be: 5 6 7 8 9 0 1
node_temp = node_root
while node_temp:
print node_temp.value,
node_temp = node_temp.right
``````