Questiontree

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;
    }
}

Leave a Reply

%d bloggers like this: