Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks

Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place.
We need to traverse all leaves and connect them by changing their left and right pointers. We also need to remove them from Binary Tree by changing left or right pointers in parent nodes. There can be many ways to solve this. In the following implementation, we add leaves at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree then the left subtree. We use return values to update left or right pointers in parent nodes.

struct Node* extractLeafList(struct Node *root, struct Node **head_ref)

{

   // Base cases

   if (root == NULL)  return NULL;

   if (root->left == NULL && root->right == NULL)

   {

       // This node is going to be added to doubly linked list

       // of leaves, set right pointer of this node as previous

       // head of DLL. We don't need to set left pointer as left

       // is already NULL

       root->right = *head_ref;

       // Change left pointer of previous head

       if (*head_ref != NULL) (*head_ref)->left = root;

       // Change head of linked list

       *head_ref = root;

       return NULL;  // Return new root

   }

   // Recur for right and left subtrees

   root->right = extractLeafList(root->right, head_ref);

   root->left  = extractLeafList(root->left, head_ref);

   return root;

}

Read full article from Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks