Powered by
/src$ make
  • Home
  • About
  • Directory
  • Contact
  • Home
  • About
  • Directory
  • Contact

Interview: Converting A Binary Tree To A Doubly Linked List (C++ Code)

9/7/2018

 

Intro - Binary Trees and Doubly Linked Lists

A popular interview question is converting a Binary Tree to a Doubly Linked List. 

A Binary Tree (BT) is a hierachical graph data structure. Here's a blog post on Trees if you've never seen one before. (Note: We don't care if it's a Binary Search Tree, it just needs to be a binary tree.)

A Doubly Linked List is a data structure where nodes that hold information are sequentially chained: each node holds a pointer to the next node in the chain. Here's a blog post on Linked Lists if you're new to them.
Picture
A binary tree (notice it's not a BST) gets converted to a doubly linked list.

BST To Doubly Linked List: Our Algorithm

Our algorithm to convert a Binary Tree to a Double Linked List is pretty simple. We'll do an In-Order Traversal of the tree (which ends up visiting the nodes in the order: 25 12 30 100 (which is the order we want our DLL to be), and we'll keep track of the current node that we're looking at, and the previous node that we've visited. 

At each step, we'll make the currentNode's left pointer point to the previousNode, and we'll make the previousNode's right pointer point to the currentNode. Simple, right?

(We'll also cover one specific case where our first node becomes the "prevNode", and we have a head pointer for our linked list point to that node.)

​See the diagram below to see how this works.
Picture
Step by Step how the algorithm works, on a simple example.

The Code (In C++)

Our code will implement the algorithm described above as one In-Order Traversal recursive function. I've also borrowed some code from previous blog posts to create/add nodes to a binary tree, and to print a linked list, so view those blog posts if you want too.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Copyright srcmake.com 2018.
// C++ Binary Tree To Doubly Linked List Code
// Official webpage for this tutorial: https://www.srcmake.com/home/bt2dll

/* Compile with:
g++ -std=c++14 main.cpp -o run
./run
*/

#include <iostream>
using namespace std;

//////////////////////////////////////////////////////
////// BINARY TREE STUFF //////
// Copying and pasting some tree code from https://www.srcmake.com/home/trees
// Our node.
struct node
    {
    int data;            // The data 
    struct node* left;    // A pointer to the node for the left child.
    struct node* right;    // A pointer to the node for the right child.
    
    node(int data)
        {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
        }
    };
/////////////////////////////////////////////////////


//////////////////////////////////////////////////////
////// LINKED LIST STUFF //////
// Copying and pasting some linked list code from https://www.srcmake.com/home/linkedlist
// Print all nodes in the list.
void PrintLinkedList(node* nodePtr)
    {
    // If this node is null, stop.
    if(nodePtr == NULL) 
        { 
        cout << endl; 
        return; 
        }
    
    // Print this node's data.
    cout << nodePtr->data << " ";
    
    // Recursively check the next node in the list.
    PrintLinkedList(nodePtr->right);
    }
//////////////////////////////////////////////////////


//////////////////////////////////////////////////////
////// BINARY TREE TO DOUBLY LINKED LIST //////
// Convert a binary tree to a doubly linked list in-place. O(1) space, O(N) time.
// Do an In-Order-Traversal and change left and right pointers of each node.
// @currNode is the node we're currently looking at.
// @prevNode is a reference (we need the value to be known to all recursive calls) to the last node we visited.
// @headPtr is a reference to the head of the linked list. (We only update this once.)
void BT2DLL(node* currNode, node*& prevNode, node*& headPtr)
    {
    /// Base case: Node doesn't exist.
    if(currNode == NULL)
        { return; }
    
    /// Left
    BT2DLL(currNode->left, prevNode, headPtr);
    
    /// Current Node
    // If this is the first node in the list...
    if(prevNode == NULL)
        {
        // Set the head pointer to point to this node. 
        headPtr = currNode;
        // Update the prevNode to be this one.
        prevNode = currNode;
        }
    // Otherwise, this isn't the first node in the list. 
    else
        {
        // Make the currentNode's left pointer point to the prevNode.
        currNode->left = prevNode;
        
        // Make the prevNode's right pointer point to the currNode.
        prevNode->right = currNode;
            
        // Update the prevNode to be this one.
        prevNode = currNode;
        }
        
    /// Right
    BT2DLL(currNode->right, prevNode, headPtr);
    }

//////////////////////////////////////////////////////

    
//////////////////////////////////////////////////////
////// MAIN //////
int main() 
    {
    cout << "Program started.\n";
    
    // First, create our binary tree. 
    node* root = new node(100);
    root->left = new node(12);
    root->left->left = new node(25);
    root->left->right = new node(30);
    
    // Create a pointer for the head of our linked list.
    // (Initially it's null.)
    node* headPtr = NULL;
    
    // The previous node that we visited doesn't exist yet.
    node* prevNode = NULL;
    
    // Now call BT2DLL.
    BT2DLL(root, prevNode, headPtr);
    
    // Print the new linked list.
    PrintLinkedList(headPtr);
        
    cout << "Program ended.\n";
    return 0;
    }
//////////////////////////////////////////////////////
The time complexity is O(N), as we visit each node exactly once, and the space complexity is O(1), since we use no extra space (since we don't create new nodes, we just update the pointers).

Conclusion

This is a popular interview question, and tests your knowledge of two fundamental data structured (binary trees and linked lists), as well as your recursive and pointer (and reference) skill, so make sure you can write this code yourself.
​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake
References:
1. Geekforfeeks.

Comments are closed.

    Author

    Hi, I'm srcmake. I play video games and develop software. 

    Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
    Metamask tip button
    License: All code and instructions are provided under the MIT License.

    Discord

    Chat with me.


    Youtube

    Watch my videos.


    Twitter

    Get the latest news.


    Twitch

    See the me code live.


    Github

    My latest projects.

Powered by Create your own unique website with customizable templates.