Extract leaves of a binary tree into a doubly-linked list
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.
The solution should process the left child before its right child for each tree node. For example,
1. Using Inorder Traversal
We can solve the problem in a single traversal of the tree by performing an inorder traversal on the tree and keeping track of the tail of the doubly linked list. For each leaf node in the inorder traversal, set the 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 118 119 120 121 |
#include <iostream> using namespace std; // Data structure to store 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; } bool is_leaf = isLeaf(root); // recur for the left subtree root->left = construct(root->left, head, tail); // if the current node is a leaf if (is_leaf) { // 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 the 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 doubly linked list is "; printDDL(head); cout << "\nPreorder traversal of the final tree is "; 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 119 120 121 122 123 124 |
// 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; } boolean isLeaf = isLeaf(root); // recur for the left subtree root.left = construct(root.left, head, tail); // if the current node is a leaf if (isLeaf) { // 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 child of the current node to the tail // of the doubly linked list root.left = tail.node; // set the right child 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 doubly linked list is "); printDDL(head.node); System.out.print("\nPreorder traversal of the final tree is "); 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 90 91 |
# Data structure to store 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 is_leaf = isLeaf(root) # recur for the left subtree (root.left, head, tail) = construct(root.left, head, tail) # if the current node is a leaf if is_leaf: # 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 child of the current node to the tail of the doubly linked list root.left = tail # set the right child 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 doubly linked list is ', end='') printDDL(head) print('\nPreorder traversal of the final tree is ', end='') preorder(root) |
Output:
Extracted doubly linked list is 8 9 5 10 11 7
Preorder traversal of the final tree is 1 2 4 3 6
Extracted doubly linked list is 8 9 5 10 11 7
Preorder traversal of the final tree is 1 2 4 3 6
2. Using Reverse Inorder Traversal
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 does that by maintaining a pointer to the linked list’s tail. We can avoid maintaining this pointer using reverse inorder 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 109 110 |
#include <iostream> using namespace std; // Data structure to store 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; } bool is_leaf = isLeaf(root); // recur for the right subtree first root->right = construct(root->right, headRef); // if the current node is a leaf if (is_leaf) { // set the right pointer of the current node to the head of the linked list root->right = headRef; // set left pointer of the linked list head 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 doubly linked list is "; printDDL(head); cout << "\nPreorder traversal of the final tree is "; 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 |
// 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; } boolean is_leaf = isLeaf(root); // recur for the right subtree first root.right = construct(root.right, head); // if the current node is a leaf if (is_leaf) { // set the right child of the current node to the head of the linked list root.right = head.node; // set left child of the linked list head 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 doubly linked list is "); printDDL(head.node); System.out.print("\nPreorder traversal of the final tree is "); 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 |
# Data structure to store 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 is_leaf = isLeaf(root) # recur for the right subtree first root.right, head = construct(root.right, head) # if the current node is a leaf if is_leaf: # set the right child of the current node to the head of the linked list root.right = head # set left child of the linked list head 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) root, head = construct(root) print('Extracted doubly linked list is ', end='') printDDL(head) print('\nPreorder traversal of the final tree is ', end='') preorder(root) |
Output:
Extracted doubly linked list is 8 9 5 10 11 7
Preorder traversal of the final tree is 1 2 4 3 6
Extracted doubly linked list is 8 9 5 10 11 7
Preorder traversal of the final tree is 1 2 4 3 6
The time complexity of both above-discussed methods is O(n) and requires O(h) extra space for the call stack, where n is the total number of nodes and h is the height of the binary tree.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)