Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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:

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.

## 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;
};

{
// 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

// Changing the left pointer of previous head to root

// Making root our new head

return NULL; //
}

// Recur for right and left subtrees

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);
}
}

{
{
cout<data<<" ";
}
}

int main()
{
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);

cout << "\nExtracted Double Linked list is:\n";

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 prev;

public Node extractLeafList(Node root)
{
if (root == null)
return null;
if (root.left == null && root.right == null)
{
{
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;
}

{
Node last = null;
{
}
}

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 : ");
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.