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

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

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.

Problem Statement Understanding

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

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

  • 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

Code Implementation

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: O(number of leaf nodes), as the doubly linked list will contain the leaf nodes.

So, in this article, we have tried to explain the most efficient approach to extract leaves of a binary tree in a doubly-linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Circular Linked List (Introduction and Applications)
Next post Merge Two Balanced Binary Trees

Leave a Reply

Your email address will not be published. Required fields are marked *