You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

# 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
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.