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

Nicholas Wong
Nicholas Wong

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.