Extract the leaves of a Binary Tree in a Doubly Linked List

Last Updated on November 23, 2022 by Prepbytes

This blog gives the complete solution with an efficient approach for solving the famous coding problem “How To Extract Leaves Of A Binary Tree In A Doubly Linked List”. Extracting leaves of a binary tree in a doubly linked list will enhance your skills in data structures like binary trees and linked lists.

How To Extract Leaves Of A Binary Tree In A Doubly Linked List

In this question, we are given a binary tree. We have to extract all the leaves of it in a Doubly Linked List. We should note that the Doubly Linked List should be created in place.

We should assume that the node structure of the doubly linked list and the binary tree is the same. What changes is the meaning of left and right pointers. In the Doubly linked list, left means the previous pointer and right means the next pointer.

A leaf node is a node which has no children. So, we have to traverse through the tree and whenever we find a leaf node, we will add it to our Doubly Linked List.

Input:
Input Binary Tree

Output:
Doubly Linked List

Modified Binary Tree

Explanation:
As the leaf nodes of the binary tree are 4, 5 and 3, they will be inserted in a doubly-linked list.

We are going to traverse through the given binary tree and whenever we reach a leaf node, we will add it to our doubly linked list. Let us have a look at the approach.

Approach How To Extract Leaves Of A Binary Tree In A Doubly Linked List

We are going to use recursion to solve this problem. If the root of the tree is NULL, then we will simply return NULL. This is going to be our base case. If the base case fails, then we will check if the current node is a leaf node or not.

If the current node is a leaf node, then we will change pointers and remove that node from the binary tree and add it to our doubly linked list. If the current node is not a leaf node, we will recur for the right and left subtrees of the node. In the end, we will simply return the root.

Algorithm How To Extract Leaves Of A Binary Tree In A Doubly Linked List

• Base case – If the root is NULL, return NULL
• If the root is a leaf node, then we will set the root’s right pointer as the previous head of the doubly linked list. We don’t need to set the left pointer as the left is already NULL
• Now, change the left pointer of the previous head I.e. the left of the head will point to root.
• Make root the new head.
• Return NULL
• If the above condition fails, then recur for the left and right subtrees.
• In the end, return root.

Dry Run How To Extract Leaves Of A Binary Tree In A Doubly Linked List

Code Implementation on How To Extract Leaves Of A Binary Tree In A Doubly Linked List

Extract the leaves of a Binary Tree in a Doubly Linked List

#include 
using namespace std;

class Node
{
    public:
    int data;
    Node *left, *right;
};
 
Node* extractLeafList(Node *root, Node **head_ref)
{
// Base case]
if (root == NULL) return NULL;
 
if (root->left == NULL && root->right == NULL)
{
    // The right of the root is going to point to the previous head
    root->right = *head_ref;
 
    // Changing the left pointer of previous head to root
    if (*head_ref != NULL) (*head_ref)->left = root;
 
    // Making root our new head
    *head_ref = root;
 
    return NULL; //
}
 
// Recur for right and left subtrees
root->right = extractLeafList(root->right, head_ref);
root->left = extractLeafList(root->left, head_ref);
 
return root;
}

Node* newNode(int data)
{
    Node* node = new Node();
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void print(Node *root)
{
    if (root != NULL)
    {
        print(root->left);
        cout<data<<" ";
        print(root->right);
    }
}

void printList(Node *head)
{
    while (head)
    {
        cout<data<<" ";
        head = head->right;
    }
}

int main()
{
    Node *head = NULL;
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
  
    cout << "Inorder Trvaersal of given Tree is:\n";
    print(root);
 
    root = extractLeafList(root, &head);
 
    cout << "\nExtracted Double Linked list is:\n";
    printList(head);
 
    cout << "\nInorder traversal of modified tree is:\n";
    print(root);
    return 0;
}

class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        right = left = null;
    }
}

public class BinaryTree
{
    Node root;
    Node head; 
    Node prev; 


    public Node extractLeafList(Node root)
    {
        if (root == null)
            return null;
        if (root.left == null && root.right == null)
        {
            if (head == null)
            {
                head = root;
                prev = root;
            }
            else
            {
                prev.right = root;
                root.left = prev;
                prev = root;
            }
            return null;
        }
        root.left = extractLeafList(root.left);
        root.right = extractLeafList(root.right);
        return root;
    }


    public void printDLL(Node head)
    {
        Node last = null;
        while (head != null)
        {
            System.out.print(head.data + " ");
            last = head;
            head = head.right;
        }
    }

    void inorder(Node node)
    {
        if (node == null)
            return;
        inorder(node.left);
        System.out.print(node.data + " ");
        inorder(node.right);
    }


    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("Inorder traversal of given tree is : ");
        tree.inorder(tree.root);
        tree.extractLeafList(tree.root);
        System.out.println("");
        System.out.println("Extracted double link list is : ");
        tree.printDLL(tree.head);
        System.out.println("");
        System.out.println("Inorder traversal of modified tree is : ");
        tree.inorder(tree.root);
    }
}

Output:
Inorder Traversal of given Tree is: 4 2 5 1 3
Extracted Double Linked list is: 4 5 3
In order traversal of the modified tree is: 2 1

Space Complexity on How To Extract Leaves Of A Binary Tree In A Doubly Linked List: O(number of leaf nodes), as the doubly linked list will contain the leaf nodes.

Linked List is a vast topic, having knowledge about data structures like linked list always give an advantage for clearing the technical interviews and in the competitive coding. For solving more questions about linked list, you can follow this link Linked List.

FAQ

1. How do you traverse a doubly linked list?
Traversing is the most common operation in case of each data structure. For this purpose, copy the head pointer in any of the temporary pointer ptr. then, traverse through the list by using a while loop.

2. How many leaves does a binary tree have?
The Full Binary Tree Theorem tells us that the number of leaves in a full binary tree is one more than the number of internal nodes. Thus, the number of new leaves that were added to create T′ is one more than the number of nodes in T.

3. Can we traverse in both directions in a doubly linked list?
The doubly linked list can be traversed in forward as well as backward directions, unlike singly linked list which can be traversed in the forward direction only. Insertion and Delete operation in a doubly-linked list are more efficient when compared to singly list when a given node is given.