Can we convert tree to doubly linked list using preorder or postorder traversal instead of inorder traversal?

Viewed 100

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.

0 Answers
Related