### 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.

### Sample Codes

# node structure
class Node:
value = None
left = None
right = None
# constructor
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

public class InterviewPractice1
{
// global
static Node node_root = null;
static Node node_temp = null;
// node structure
private static class Node
{
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right)
{
this.value = value;
this.left = left;
this.right = right;
}
}
// visit
private static void visit(Node node)
{
if (node_temp == null) node_root = node; // set head
else node_temp.right = node; // make right of temp to this node
node.left = node_temp; // make temp to the left of this node
node_temp = node; // next node
}
// depth first, recursive
private static void depth_first_recursive_traversal_in_order(Node node)
{
if (node == null) return;
depth_first_recursive_traversal_in_order(node.left);
visit(node);
depth_first_recursive_traversal_in_order(node.right);
}
// main
public static void main(String[] args)
{
// tree
Node node_5 = new Node(5, null, null);
Node node_7 = new Node(7, null, null);
Node node_9 = new Node(9, null, null);
Node node_1 = new Node(1, null, null);
Node node_6 = new Node(6, node_5, node_7);
Node node_0 = new Node(0, node_9, node_1);
Node node_8 = new Node(8, node_6, node_0);
// run
node_root = node_8;
depth_first_recursive_traversal_in_order(node_root);
// the result should be 5 6 7 8 9 0 1
node_temp = node_root;
while (node_temp != null) {
System.out.print(node_temp.value + " ");
node_temp = node_temp.right;
}
}
}

#include <iostream>
struct Node
{
int value;
Node *left;
Node *right;
Node(int value, Node *left = NULL, Node *right = NULL)
{
this->value = value;
this->left = left;
this->right = right;
}
};
Node *node_root = NULL;
Node *node_temp = NULL;
void visit(Node *node)
{
if (node_temp == NULL) node_root = node; // set head
else node_temp->right = node; // make right of them to this node
node->left = node_temp; // make temp to the left of this node
node_temp = node; // next node
}
void depth_first_recursive_traversal_in_order(Node *node)
{
if (!node) return;
depth_first_recursive_traversal_in_order(node->left);
visit(node);
depth_first_recursive_traversal_in_order(node->right);
}
int main()
{
// tree
Node *node_5 = new Node(5);
Node *node_7 = new Node(7);
Node *node_9 = new Node(9);
Node *node_1 = new Node(1);
Node *node_6 = new Node(6, node_5, node_7);
Node *node_0 = new Node(0, node_9, node_1);
Node *node_8 = new Node(8, node_6, node_0);
// conversion
node_root = node_8;
node_temp = NULL; // null
depth_first_recursive_traversal_in_order(node_8);
// answer should be: 5 6 7 8 9 0 1
node_temp = node_root;
while (node_temp) {
printf("%d ", node_temp->value);
node_temp = node_temp->right;
}
}

### Like this:

Like Loading...