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.
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.
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.
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).
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.
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.
License: All code and instructions are provided under the MIT License.