Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Algorithm
3.2.
Code
3.3.
Time Complexity
3.4.
Space Complexity
4.
4.1.
What is the time complexity of inserting a node in a Binary Search Tree?
4.2.
What is the time complexity of insertion in a Doubly Linked List?
5.
Conclusion
Last Updated: Mar 27, 2024

# Extract Leaves of a Binary Tree in a Doubly Linked List

Saksham Gupta
0 upvote

## Introduction

Binary trees and linked list are the two most famous topics in data structures when it comes to tech interviews but what is more interesting is the combination of these two, Yes today, we will be combining binary trees with the linked list and will be solving the problem, Extract Leaves of a Binary Tree in a Doubly Linked List. A doubly linked list is a linked list that stores the address of its next as well as previous pointers. You can read more about them at Coding Ninjas Blog.

## Problem Statement

We have been given a binary tree. Our task is first to extract all the leaf nodes of the given tree and then convert them into a doubly-linked list.

Let’s take a look at the following example.

Let’s say this is the binary tree given to us.

Then our output will be the following:

Modified Binary Tree:

Explanation

As 3,7 are the leaf nodes of the given binary tree, thus these are extracted to form a doubly-linked list starting from the leftmost leaf node as the head and the rightmost leaf node as the tail.

## Approach

The approach to the following question is going to be fairly simple. We will use recursion to traverse the tree and once we reach a leaf node, we will remove it from the binary tree and will insert it into our doubly linked list. Also, we will be traversing in the right to left direction, i.e., in the recursive calls, we will first make a call to the right part and then to the left part. You’ll understand the reason for this once you read the algorithm.

Parameters and Function Defined:

1. A function named extract() will take the ‘ROOT’ of a binary tree as input and will return the root of the modified tree.
2. ‘HEAD’ node, which will be the head of our doubly linked list.

### Algorithm

1. Base Case:
1. If the ‘ROOT’ is NULL, return NULL.
2. If the ‘ROOT’ is a leaf node:
1. We will be including this node in our doubly linked list and will be removing this from the tree. For that, we will set the right pointer of this node to the previous head of the doubly linked list. Now left of the previous head will be set to the ‘ROOT’ (if the previous head is not NULL).
2. Now, ‘ROOT’ will be our new head (this is the reason we are traversing from right to left, and in the end, the node we are left with is going to be our head).
3. Return NULL (as we have to delete this node from the tree).
3. If the root is not a leaf node:
1. We will make two recursive calls to the same function for the right and left part.
4. Return final ‘ROOT’ of the modified tree.

Below is the code for the above algorithm.

### Code

``````#include <iostream>
using namespace std;

// Binary tree node class.
class Node
{
public:
int data;
Node *left, *right;

Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};

// Head of the doubly linked list.

// Function to extract the leave nodes in a doubly linked list.
Node *extract(Node *root)
{
// Base Case.
if (root == NULL)
{
return NULL;
}

// Checking if 'ROOT' is a leaf node or not.
if (!root->left && !root->left)
{
// The right pointer of the 'ROOT' node is set to the previous head of the doubly linked list.

// Left of the previous head is set to 'ROOT'(if it is not NULL).
if (headFinal != NULL)
{
}

// 'ROOT' will be our new head of the doubly linked list.

return NULL;
}

// Recursive calls for the remaining tree.
root->right = extract(root->right);
root->left = extract(root->left);

return root;
}

// Printing the pre order traversal of the binary tree.
void printPreOrder(Node *root)
{
if (root == NULL)
{
return;
}
printPreOrder(root->left);
cout << root->data << " ";
printPreOrder(root->right);
}

// Printing the doubly linked list.
{
Node *temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->right;
}
cout << endl;
}

int main()
{
Node *root = new Node(5);
root->left = new Node(4);
root->right = new Node(6);
root->left->left = new Node(3);
root->right->right = new Node(7);

// Call the extract Function.
root = extract(root);

// Printing the doubly linked list.
cout << "Doubly Linked List: " << endl;

// Printing the modified tree.
cout << "Pre order for the modified tree: " << endl;
printPreOrder(root);
return 0;
}``````

Input

``5 4 7 6 3``

Output

``````Doubly Linked List
3 7
Pre Order for the modified tree
4 5 6``````

Note: Input is shown as the pre-order traversal of the tree.

### Time Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

As we are traversing the tree only once thus, the time complexity is O(N).

### Space Complexity

O(X), where ‘X’ is the number of leaf nodes present in the binary tree.

As we are making a new doubly linked list of size ‘X’, the space complexity O(X).

## Frequently Asked Questions(FAQs)

### What is the time complexity of inserting a node in a Binary Search Tree?

The best case time complexity is O(log(N)) where N is the number of Nodes whereas in the case of a skewed BST, the time complexity could be up to O(N)

### What is the time complexity of insertion in a Doubly Linked List?

O(N) where N is the size of the Linked List

## Conclusion

We saw how we could extract leaf nodes and convert them into a doubly-linked list using recursion. We modified the given tree and removed the leaf nodes as well, and returned the modified tree. Now that you have understood how to extract leaves of a binary tree in a doubly linked list, your confidence on the topic of Binary trees and linked lists would surely be high, but high confidence should not turn into overconfidence, and for that, one needs to practice regularly. But with coding ninjas, you don’t have to worry.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass