Conversion using inorder traversal
Here we are traversing the tree in inorder fashion and changing it's left and right pointer to next and previous.
// A C++ program for in-place conversion of Binary Tree to DLL
#include <iostream>
using namespace std;
/* A binary tree node has data, and left and right pointers */
struct node
{
int data;
node* left;
node* right;
};
// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
// Base case
if (root == NULL) return;
// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL;
// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root->left, head);
// Now convert this node
if (prev == NULL)
*head = root;
else
{
root->left = prev;
prev->right = root;
}
prev = root;
// Finally convert right subtree
BinaryTree2DoubleLinkedList(root->right, head);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* new_node = new node;
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}
/* Function to print nodes in a given doubly linked list */
void printList(node *node)
{
while (node!=NULL)
{
cout << node->data << " ";
node = node->right;
}
}
/* Driver program to test above functions*/
int main()
{
// Let us create the tree shown in above diagram
node *root = newNode(10);
root->left = newNode(12);
root->right = newNode(15);
root->left->left = newNode(25);
root->left->right = newNode(30);
root->right->left = newNode(36);
// Convert to DLL
node *head = NULL;
BinaryTree2DoubleLinkedList(root, &head);
// Print the converted list
printList(head);
return 0;
}
If the interviewer asks is it possible to make list in a preorder or postorder fashion. What would be the
answer?
If yes then how?
I think we can traverse the tree in a preorder fashion and make a doubly linked list out of it. But how do I explain it to her.