Construct a doubly linked list out of a ternary tree.

1.	Construct a doubly linked list out of a ternary tree.
Answer» A ternary tree is similar to a binary tree, except that instead of two nodes, it has three: LEFT, middle, and right. The ATTRIBUTES of the doubly linked list should be as follows: The ternary tree's left pointer should be used as the previous pointer in a doubly-linked list. The ternary tree's middle pointer should not point to anything. The ternary tree's right pointer should be the doubly linked list's next pointer. Each ternary tree node is entered into a doubly-linked list before its subtrees, with the left child of each node being inserted first, followed by the middle and right child (if any). The approach is to make a preorder traversal of the tree. When we visit a node, we will use a tail pointer to INSERT it into a doubly-linked list at the end. That's how we keep the required insertion order. Then, in that order, we call for the left child, middle child, and right child. Implementation: //Utility function that creates a doubly linked list//by inserting the current node at the end of the doubly//linked list by employing a tail pointervoid push(Node** tail_reference, Node* n){ // the tail pointer is to be initialized if (tail_reference == NULL) { tail_reference = n; // set left, middle and right child to point // to NULL n->left = NULL; n->middle = NULL; n->right = NULL; return; } // using tail pointer, insert node in the end (tail_reference)->right = n; // the middle and right child are set to point to NULL n->right = NULL; n->middle = NULL; // set previous of the node n->left = (tail_reference); // now tail pointer is pointing to the inserted node (tail_reference) = n;}// From a ternary tree, create a doubly linked list,// by making a preorder traversal of the treeNode ternaryTreeToList(Node** head_reference, Node* root){ // Base case if (!root) return NULL; //a static tail pointer to be created static Node* tail = NULL; // left, middle and right nodes to be stored // for FUTURE calls. Node* left = root->left; Node* middle = root->middle; Node* right = root->right; // set the head of the doubly linked list // as the root of the ternary tree if (head_reference == NULL) head_reference = root; // push the current node in the end of the doubly linked list push(&tail, root); //recursion for left, middle and right child ternaryTreeToList(head_reference, left); ternaryTreeToList(head_reference, middle); ternaryTreeToList(head_reference, right);} Time COMPLEXITY: O(n) Space Complexity: O(1)

Answer»

A ternary tree is similar to a binary tree, except that instead of two nodes, it has three: LEFT, middle, and right.

The ATTRIBUTES of the doubly linked list should be as follows:

The ternary tree's left pointer should be used as the previous pointer in a doubly-linked list.
The ternary tree's middle pointer should not point to anything.
The ternary tree's right pointer should be the doubly linked list's next pointer.
Each ternary tree node is entered into a doubly-linked list before its subtrees, with the left child of each node being inserted first, followed by the middle and right child (if any).

The approach is to make a preorder traversal of the tree. When we visit a node, we will use a tail pointer to INSERT it into a doubly-linked list at the end. That's how we keep the required insertion order. Then, in that order, we call for the left child, middle child, and right child.

Implementation:

//Utility function that creates a doubly linked list//by inserting the current node at the end of the doubly//linked list by employing a tail pointervoid push(Node** tail_reference, Node* n){ // the tail pointer is to be initialized if (*tail_reference == NULL) { *tail_reference = n; // set left, middle and right child to point // to NULL n->left = NULL; n->middle = NULL; n->right = NULL; return; } // using tail pointer, insert node in the end (*tail_reference)->right = n; // the middle and right child are set to point to NULL n->right = NULL; n->middle = NULL; // set previous of the node n->left = (*tail_reference); // now tail pointer is pointing to the inserted node (*tail_reference) = n;}// From a ternary tree, create a doubly linked list,// by making a preorder traversal of the treeNode* ternaryTreeToList(Node** head_reference, Node* root){ // Base case if (!root) return NULL; //a static tail pointer to be created static Node* tail = NULL; // left, middle and right nodes to be stored // for FUTURE calls. Node* left = root->left; Node* middle = root->middle; Node* right = root->right; // set the head of the doubly linked list // as the root of the ternary tree if (*head_reference == NULL) *head_reference = root; // push the current node in the end of the doubly linked list push(&tail, root); //recursion for left, middle and right child ternaryTreeToList(head_reference, left); ternaryTreeToList(head_reference, middle); ternaryTreeToList(head_reference, right);}

Time COMPLEXITY: O(n)
Space Complexity: O(1)

Construct a doubly linked list out of a ternary tree.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment