Given a binary tree, extract all its leaves into a doubly linked list, i.e., remove all leaf nodes from the binary tree and construct a doubly linked list out of them.
The extraction should be by rearranging the pointers of the binary tree such that the left pointer should act as the previous pointer and the right pointer should serve as the next pointer for the doubly linked list node.
For example,
The problem can be solved in a single traversal of the tree by performing an in-order traversal on the tree and keeping track of the tail of the doubly linked list. Each leaf node in the in-order traversal, set its left pointer to tail and tail’s right pointer to the current leaf node. Also, update the corresponding left or right pointer of the parent node to null to remove the leaf nodes from the binary tree.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Traverse a given binary tree using the preorder traversal
void preorder(Node* root)
{
if (root == nullptr) {
return;
}
cout << root->data << ‘ ‘;
preorder(root->left);
preorder(root->right);
}
// Print the given doubly linked list from left to right
void printDDL(Node* head)
{
while (head)
{
cout << head->data << ‘ ‘;
head = head->right;
}
}
// Returns true if the given tree node is a leaf; false otherwise
bool isLeaf(Node* root) {
return root != nullptr && root->left == nullptr && root->right == nullptr;
}
// Function to extract leaves of a Binary Tree into a Doubly Linked List
Node* construct(Node* root, Node* &head, Node* &tail)
{
// base case
if (root == nullptr) {
return nullptr;
}
// recur for the left subtree
root->left = construct(root->left, head, tail);
// if current node is a leaf
if (isLeaf(root))
{
// This is true only for the leftmost leaf node
if (head == nullptr) {
// point the head of the doubly linked list to the
// current leaf node and initialize the tail pointer
head = tail = root;
} else {
// set left pointer of the current node to the tail
// of the doubly linked list
root->left = tail;
// set right pointer of the tail to the current node
tail->right = root;
// update the tail
tail = root;
}
// return null to remove the current node from the binary tree
return nullptr;
}
// recur for the right subtree
root->right = construct(root->right, head, tail);
// return the root node
return root;
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
root->right->left->left = new Node(10);
root->right->left->right = new Node(11);
// to keep track of the head of the doubly linked list
Node* head = nullptr;
// to keep track of the tail of the doubly linked list
Node* tail = nullptr;
root = construct(root, head, tail);
cout << “Extracted Double Linked list:tt”;
printDDL(head);
cout << “nPreorder traversal of final tree:t”;
preorder(root);
return 0;
}
|
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
// A Binary Tree Node
class Node
{
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
class Main {
// Wrapper over Node class
static class NodeWrapper {
public Node node;
}
// Traverse a given binary tree using the preorder traversal
public static void preorder(Node root)
{
if (root == null) {
return;
}
System.out.print(root.data + ” “);
preorder(root.left);
preorder(root.right);
}
// Print the given doubly linked list from left to right
public static void printDDL(Node head)
{
while (head != null) {
System.out.print(head.data + ” “);
head = head.right;
}
}
// Returns true if the given tree node is a leaf; false otherwise
public static boolean isLeaf(Node root) {
return root != null && root.left == null && root.right == null;
}
// Function to extract leaves of a Binary Tree into a Doubly Linked List
public static Node construct(Node root, NodeWrapper head, NodeWrapper tail)
{
// base case
if (root == null) {
return null;
}
// recur for the left subtree
root.left = construct(root.left, head, tail);
// if current node is a leaf
if (isLeaf(root))
{
// This is true only for the leftmost leaf node
if (head.node == null) {
// point the head of the doubly linked list to the
// current leaf node and initialize the tail pointer
head.node = tail.node = root;
} else {
// set left pointer of the current node to the tail
// of the doubly linked list
root.left = tail.node;
// set right pointer of the tail to the current node
tail.node.right = root;
// update the tail
tail.node = root;
}
// return null to remove the current node from the binary tree
return null;
}
// recur for the right subtree
root.right = construct(root.right, head, tail);
// return the root node
return root;
}
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.right.left.left = new Node(10);
root.right.left.right = new Node(11);
// to keep track of the head of the doubly linked list
NodeWrapper head = new NodeWrapper();
// to keep track of the tail of the doubly linked list
NodeWrapper tail = new NodeWrapper();
root = construct(root, head, tail);
System.out.print(“Extracted Double Linked list: “);
printDDL(head.node);
System.out.print(“nPreorder traversal of final tree: “);
preorder(root);
}
}
|
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
# A Binary Tree Node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Traverse a given binary tree using the preorder traversal
def preorder(root):
if root is None:
return
print(root.data, end=‘ ‘)
preorder(root.left)
preorder(root.right)
# Print the given doubly linked list from left to right
def printDDL(head):
while head:
print(head.data, end=‘ ‘)
head = head.right
# Returns true if the given tree node is a leaf; false otherwise
def isLeaf(root):
return root is not None and root.left is None and root.right is None
# Function to extract leaves of a Binary Tree into a Doubly Linked List.
# `head` & `tail` keep track of the head and tail of the doubly linked list
def construct(root, head=None, tail=None):
# base case
if root is None:
return None, head, tail
# recur for the left subtree
(root.left, head, tail) = construct(root.left, head, tail)
# if current node is a leaf
if isLeaf(root):
# This is true only for the leftmost leaf node
if head is None:
# point the head of the doubly linked list to the current leaf node and
# initialize the tail pointer
head = tail = root
else:
# set left pointer of the current node to the tail of the doubly linked list
root.left = tail
# set right pointer of the tail to the current node
tail.right = root
# update the tail
tail = root
# return None to remove the current node from the binary tree
return None, head, tail
# recur for the right subtree
root.right, head, tail = construct(root.right, head, tail)
# return the root node
return root, head, tail
if __name__ == ‘__main__’:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.right.left.left = Node(10)
root.right.left.right = Node(11)
root, head, tail = construct(root)
print(“Extracted Double Linked list:”, end=‘tt’)
printDDL(head)
print(“nPreorder traversal of final tree:”, end=‘t’)
preorder(root)
|
Output:
Extracted Double Linked list: 8 9 5 10 11 7
Preorder traversal of final tree: 1 2 4 3 6
Extracted Double Linked list: 8 9 5 10 11 7
Preorder traversal of final tree: 1 2 4 3 6
The above solution processes the leaf nodes from left to right and efficiently inserts the leaf nodes at the end of the doubly linked list; it maintains a pointer to the linked list’s tail. We can avoid maintaining this pointer by reverse-in-order traversal where the right subtree is processed before the left subtree. Now, we can easily insert each encountered node at the beginning of the list.
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Traverse a given binary tree using the preorder traversal
void preorder(Node* root)
{
if (root == nullptr) {
return;
}
cout << root->data << ‘ ‘;
preorder(root->left);
preorder(root->right);
}
// Print the given doubly linked list from left to right
void printDDL(Node* head)
{
while (head)
{
cout << head->data << ‘ ‘;
head = head->right;
}
}
// Returns true if the given tree node is a leaf; false otherwise
bool isLeaf(Node* root) {
return root != nullptr && root->left == nullptr && root->right == nullptr;
}
// Function to extract leaves of a Binary Tree into a Doubly Linked List
Node* construct(Node* root, Node* &headRef)
{
// base case
if (root == nullptr) {
return nullptr;
}
// recur for the right subtree first
root->right = construct(root->right, headRef);
// if current node is a leaf
if (isLeaf(root))
{
// set right pointer of the current node to the head of the linked list
root->right = headRef;
// set left pointer of head of the linked list to the current node
if (headRef != nullptr) {
headRef->left = root;
}
// update head of the linked list to the current node
headRef = root;
// return null to remove the current node from the binary tree
return nullptr;
}
// recur for the left subtree
root->left = construct(root->left, headRef);
// return the root node
return root;
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
root->right->left->left = new Node(10);
root->right->left->right = new Node(11);
// to keep track of the head of the doubly linked list
Node* head = nullptr;
root = construct(root, head);
cout << “Extracted Double Linked list:tt”;
printDDL(head);
cout << “nPreorder traversal of final tree:t”;
preorder(root);
return 0;
}
|
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
// A Binary Tree Node
class Node
{
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
class Main {
// Wrapper over Node class
static class NodeWrapper {
public Node node;
}
// Traverse a given binary tree using the preorder traversal
public static void preorder(Node root)
{
if (root == null) {
return;
}
System.out.print(root.data + ” “);
preorder(root.left);
preorder(root.right);
}
// Print the given doubly linked list from left to right
public static void printDDL(Node head)
{
while (head != null) {
System.out.print(head.data + ” “);
head = head.right;
}
}
// Returns true if the given tree node is a leaf; false otherwise
public static boolean isLeaf(Node root) {
return root != null && root.left == null && root.right == null;
}
// Function to extract leaves of a Binary Tree into a Doubly Linked List
public static Node construct(Node root, NodeWrapper head)
{
// base case
if (root == null) {
return null;
}
// recur for the right subtree first
root.right = construct(root.right, head);
// if current node is a leaf
if (isLeaf(root))
{
// set right pointer of the current node to the head of the linked list
root.right = head.node;
// set left pointer of head of the linked list to the current node
if (head.node != null) {
head.node.left = root;
}
// update head of the linked list to the current node
head.node = root;
// return null to remove the current node from the binary tree
return null;
}
// recur for the left subtree
root.left = construct(root.left, head);
// return the root node
return root;
}
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.right.left.left = new Node(10);
root.right.left.right = new Node(11);
// to keep track of the head of the doubly linked list
NodeWrapper head = new NodeWrapper();
root = construct(root, head);
System.out.print(“Extracted Double Linked list: “);
printDDL(head.node);
System.out.print(“nPreorder traversal of final tree: “);
preorder(root);
}
}
|
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
# A Binary Tree Node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Traverse a given binary tree using the preorder traversal
def preorder(root):
if root is None:
return
print(root.data, end=‘ ‘)
preorder(root.left)
preorder(root.right)
# Print the given doubly linked list from left to right
def printDDL(head):
while head:
print(head.data, end=‘ ‘)
head = head.right
# Returns true if the given tree node is a leaf; false otherwise
def isLeaf(root):
return root is not None and root.left is None and root.right is None
# Function to extract leaves of a Binary Tree into a Doubly Linked List
def construct(root, head=None):
# base case
if root is None:
return None, head
# recur for the right subtree first
root.right, head = construct(root.right, head)
# if current node is a leaf
if isLeaf(root):
# set right pointer of the current node to the head of the linked list
root.right = head
# set left pointer of head of the linked list to the current node
if head:
head.left = root
# update head of the linked list to the current node
# return `None` to remove the current node from the binary tree
return None, root
# recur for the left subtree
root.left, head = construct(root.left, head)
# return the root node
return root, head
if __name__ == ‘__main__’:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.right.left.left = Node(10)
root.right.left.right = Node(11)
# to keep track of the head of the doubly linked list
root, head = construct(root)
print(“Extracted Double Linked list:tt”, end=”)
printDDL(head)
print(“nPreorder traversal of final tree:t”, end=”)
preorder(root)
|
Output:
Extracted Double Linked list: 8 9 5 10 11 7
Preorder traversal of final tree: 1 2 4 3 6
Extracted Double Linked list: 8 9 5 10 11 7
Preorder traversal of final tree: 1 2 4 3 6