InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Extract all leaves from a Binary Tree into a Doubly Linked List (DLL). |
|
Answer» It's worth noting that the DLL must be created in place. Assume that the DLL and Binary Tree node structures are identical, with the exception that the meanings of the left and right pointers. Left denotes the previous pointer, whereas right denotes the next pointer in DLL. All of the leaves must be traversed and connected by ADJUSTING the left and right pointers. By adjusting the left or right pointers in parent NODES, we can also delete them from the Binary Tree. There are NUMEROUS options for resolving this issue. We add leaves to the beginning of the current linked list and update the list's head using the pointer to head pointer in the following code. We must process leaves in reverse order because we insert from the beginning. We traverse the right subtree first, then the left subtree, in reverse order. To update the left and right pointers in parent nodes, we employ RETURN values. Implementation: // The function extracts all the// leaves from a given Binary Tree.// The function returns new root of// the Binary Tree. The function also sets// *head_reference as the head of the DLL.// The left pointer of the tree is used as prev // and the right pointer is used as next in the DLL.Node* extractLeaf(Node **head_reference, Node *root){ if (!root) return NULL; if (root->right == NULL && root->left == NULL) { // This node will be added to the doubly linked // list of leaves. We will have to // set the right pointer of this node // as the previous head of DLL. We // don't need to set the left pointer // as the left is already NULL. root->right = *head_reference; // Change the left pointer of previous head if (*head_reference) (*head_reference)->left = root; // Change the head of the linked list *head_reference = root; return NULL; } // Recursion for right and left SUBTREES root->right = extractLeaf(&head_reference, root->right); root->left = extractLeaf(&head_reference, root->lef); return root;}Time Complexity: O(n) |
|