Convert a given Binary Tree to Doubly Linked List | Set 1
Given a Binary Tree [Bt], convert it to a Doubly Linked List[DLL]. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal [leftmost node in BT] must be the head node of the DLL.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
I came across this question during one of my interviews. A similar problem has been discussed in this post.
The problem here is simpler as we don’t need to create a circular DLL, but a simple DLL. The idea behind its solution is quite simple and straight.
- If the left subtree exists, process the left subtree
- Recursively convert the left subtree to DLL.
- Then find the inorder predecessor of the root in the left subtree [the inorder predecessor is the rightmost node in the left subtree].
- Make the inorder predecessor as the previous root and the root as the next in order predecessor.
-
If the right subtree exists, process the right subtree [Below 3 steps are similar to the left subtree].
- Recursively convert the right subtree to DLL.
- Then find the inorder successor of the root in the right subtree [in order the successor is the leftmost node in the right subtree].
- Make the inorder successor as the next root and the root as the previous inorder successor.
- Find the leftmost node and return it [the leftmost node is always the head of a converted DLL].
Below is the source code for the above algorithm.
C++
|
// A C++ program for in-place // conversion of Binary Tree to DLL #include using namespace std; /* A binary tree node has data, and left and right pointers */ class node { public: int data; node* left; node* right; }; /* This is the core function to convert Tree to list. This function follows steps 1 and 2 of the above algorithm */ node* bintree2listUtil[node* root] { // Base case if [root == NULL] return root; // Convert the left subtree and link to root if [root->left != NULL] { // Convert the left subtree node* left = bintree2listUtil[root->left]; // Find inorder predecessor. After this loop, left // will point to the inorder predecessor for [; left->right != NULL; left = left->right] ; // Make root as next of the predecessor left->right = root; // Make predecessor as previous of root root->left = left; } // Convert the right subtree and link to root if [root->right != NULL] { // Convert the right subtree node* right = bintree2listUtil[root->right]; // Find inorder successor. After this loop, right // will point to the inorder successor for [; right->left != NULL; right = right->left] ; // Make root as previous of successor right->left = root; // Make successor as next of root root->right = right; } return root; } // The main function that first calls // bintree2listUtil[], then follows step 3 // of the above algorithm node* bintree2list[node* root] { // Base case if [root == NULL] return root; // Convert to DLL using bintree2listUtil[] root = bintree2listUtil[root]; // bintree2listUtil[] returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost // node while [root->left != NULL] root = root->left; return [root]; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode[int data] { node* new_node = new node[]; new_node->data = data; new_node->left = new_node->right = NULL; return [new_node]; } /* Function to print nodes in a given doubly linked list */ void printList[node* node] { while [node != NULL] { cout data right; } } /* Driver code*/ int main[] { // Let us create the tree shown in above diagram node* root = newNode[10]; root->left = newNode[12]; root->right = newNode[15]; root->left->left = newNode[25]; root->left->right = newNode[30]; root->right->left = newNode[36]; // Convert to DLL node* head = bintree2list[root]; // Print the converted list printList[head]; return 0; } // This code is contributed by rathbhupendra |
C
|
// A C program for in-place conversion of Binary Tree to DLL #include /* A binary tree node has data, and left and right pointers */ struct node { int data; node* left; node* right; }; /* This is the core function to convert Tree to list. This function follows steps 1 and 2 of the above algorithm */ node* bintree2listUtil[node* root] { // Base case if [root == NULL] return root; // Convert the left subtree and link to root if [root->left != NULL] { // Convert the left subtree node* left = bintree2listUtil[root->left]; // Find inorder predecessor. After this loop, left // will point to the inorder predecessor for [; left->right!=NULL; left=left->right]; // Make root as next of the predecessor left->right = root; // Make predecessor as previous of root root->left = left; } // Convert the right subtree and link to root if [root->right!=NULL] { // Convert the right subtree node* right = bintree2listUtil[root->right]; // Find inorder successor. After this loop, right // will point to the inorder successor for [; right->left!=NULL; right = right->left]; // Make root as previous of successor right->left = root; // Make successor as next of root root->right = right; } return root; } // The main function that first calls bintree2listUtil[], then follows step 3 // of the above algorithm node* bintree2list[node *root] { // Base case if [root == NULL] return root; // Convert to DLL using bintree2listUtil[] root = bintree2listUtil[root]; // bintree2listUtil[] returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost node while [root->left != NULL] root = root->left; return [root]; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode[int data] { node* new_node = new node; new_node->data = data; new_node->left = new_node->right = NULL; return [new_node]; } /* Function to print nodes in a given doubly linked list */ void printList[node *node] { while [node!=NULL] { printf["%d ", node->data]; node = node->right; } } /* Driver program to test above functions*/ int main[] { // Let us create the tree shown in above diagram node *root = newNode[10]; root->left = newNode[12]; root->right = newNode[15]; root->left->left = newNode[25]; root->left->right = newNode[30]; root->right->left = newNode[36]; // Convert to DLL node *head = bintree2list[root]; // Print the converted list printList[head]; return 0; } |
Java
|
// Java program to convert binary tree to double linked list
/* A binary tree node has data, and left and right pointers */ class Node { int data; Node left, right;
Node[int item] { data = item; left = right = null; } }
class BinaryTree { Node root; /* This is the core function to convert Tree to list. This function follows steps 1 and 2 of the above algorithm */
Node bintree2listUtil[Node node] { // Base case if [node == null] return node;
// Convert the left subtree and link to root if [node.left != null] { // Convert the left subtree Node left = bintree2listUtil[node.left];
// Find inorder predecessor. After this loop, left // will point to the inorder predecessor for [; left.right != null; left = left.right];
// Make root as next of the predecessor left.right = node;
// Make predecessor as previous of root node.left = left; }
// Convert the right subtree and link to root if [node.right != null] { // Convert the right subtree Node right = bintree2listUtil[node.right];
// Find inorder successor. After this loop, right // will point to the inorder successor for [; right.left != null; right = right.left];
// Make root as previous of successor right.left = node;
// Make successor as next of root node.right = right; }
return node; }
// The main function that first calls bintree2listUtil[], then follows // step 3 of the above algorithm
Node bintree2list[Node node] { // Base case if [node == null] return node;
// Convert to DLL using bintree2listUtil[] node = bintree2listUtil[node];
// bintree2listUtil[] returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost node while [node.left != null] node = node.left;
return node; }
/* Function to print nodes in a given doubly linked list */ void printList[Node node] { while [node != null] { System.out.print[node.data + " "]; node = node.right; } }
/* Driver program to test above functions*/ public static void main[String[] args] { BinaryTree tree = new BinaryTree[];
// Let us create the tree shown in above diagram tree.root = new Node[10]; tree.root.left = new Node[12]; tree.root.right = new Node[15]; tree.root.left.left = new Node[25]; tree.root.left.right = new Node[30]; tree.root.right.left = new Node[36];
// Convert to DLL Node head = tree.bintree2list[tree.root];
// Print the converted list tree.printList[head]; } } |
Python3
|
# Python program to convert # binary tree to doubly linked list class Node[object]:
"""Binary tree Node class has data, left and right child""" def __init__[self, item]: self.data = item self.left = None self.right = None def BTToDLLUtil[root]:
"""This is a utility function to convert the binary tree to doubly linked list. Most of the core task is done by this function.""" if root is None: return root # Convert left subtree # and link to root if root.left:
# Convert the left subtree left = BTToDLLUtil[root.left] # Find inorder predecessor, After # this loop, left will point to the # inorder predecessor of root while left.right: left = left.right # Make root as next of predecessor left.right = root
# Make predecessor as # previous of root root.left = left # Convert the right subtree # and link to root if root.right:
# Convert the right subtree right = BTToDLLUtil[root.right] # Find inorder successor, After # this loop, right will point to # the inorder successor of root while right.left: right = right.left # Make root as previous # of successor right.left = root
# Make successor as # next of root root.right = right return root def BTToDLL[root]: if root is None: return root # Convert to doubly linked # list using BLLToDLLUtil root = BTToDLLUtil[root]
# We need pointer to left most # node which is head of the # constructed Doubly Linked list while root.left: root = root.left return root def print_list[head]:
"""Function to print the given doubly linked list""" if head is None: return while head: print[head.data, end = " "] head = head.right # Driver Code if __name__ == '__main__': root = Node[10] root.left = Node[12] root.right = Node[15] root.left.left = Node[25] root.left.right = Node[30] root.right.left = Node[36] head = BTToDLL[root] print_list[head] # This code is contributed # by viveksyngh |
C#
|
using System; // C# program to convert binary tree to double linked list /* A binary tree node has data, and left and right pointers */ public class Node { public int data; public Node left, right; public Node[int item] { data = item; left = right = null; } } public class BinaryTree { public Node root; /* This is the core function to convert Tree to list. This function follows steps 1 and 2 of the above algorithm */ public virtual Node bintree2listUtil[Node node] { // Base case if [node == null] { return node; } // Convert the left subtree and link to root if [node.left != null] { // Convert the left subtree Node left = bintree2listUtil[node.left]; // Find inorder predecessor. After this loop, left // will point to the inorder predecessor for [; left.right != null; left = left.right] { ; } // Make root as next of the predecessor left.right = node; // Make predecessor as previous of root node.left = left; } // Convert the right subtree and link to root if [node.right != null] { // Convert the right subtree Node right = bintree2listUtil[node.right]; // Find inorder successor. After this loop, right // will point to the inorder successor for [; right.left != null; right = right.left] { ; } // Make root as previous of successor right.left = node; // Make successor as next of root node.right = right; } return node; } // The main function that first calls bintree2listUtil[], then follows // step 3 of the above algorithm public virtual Node bintree2list[Node node] { // Base case if [node == null] { return node; } // Convert to DLL using bintree2listUtil[] node = bintree2listUtil[node]; // bintree2listUtil[] returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost node while [node.left != null] { node = node.left; } return node; } /* Function to print nodes in a given doubly linked list */ public virtual void printList[Node node] { while [node != null] { Console.Write[node.data + " "]; node = node.right; } } /* Driver program to test above functions*/ public static void Main[string[] args] { BinaryTree tree = new BinaryTree[]; // Let us create the tree shown in above diagram tree.root = new Node[10]; tree.root.left = new Node[12]; tree.root.right = new Node[15]; tree.root.left.left = new Node[25]; tree.root.left.right = new Node[30]; tree.root.right.left = new Node[36]; // Convert to DLL Node head = tree.bintree2list[tree.root]; // Print the converted list tree.printList[head]; } } // This code is contributed by Shrikant13 |
Javascript
|
// javascript program to convert binary tree to double linked list /* A binary tree node has data, and left and right pointers */ class Node { constructor[val] { this.data = val; this.left = null; this.right = null; } } var root; /* * This is the core function to convert Tree to list. This function follows * steps 1 and 2 of the above algorithm */ function bintree2listUtil[node] { // Base case if [node == null] return node; // Convert the left subtree and link to root if [node.left != null] { // Convert the left subtree var left = bintree2listUtil[node.left]; // Find inorder predecessor. After this loop, left // will point to the inorder predecessor for [; left.right != null; left = left.right]
// Make root as next of the predecessor left.right = node; // Make predecessor as previous of root node.left = left; } // Convert the right subtree and link to root if [node.right != null] { // Convert the right subtree var right = bintree2listUtil[node.right]; // Find inorder successor. After this loop, right // will point to the inorder successor for [; right.left != null; right = right.left]
// Make root as previous of successor right.left = node; // Make successor as next of root node.right = right; } return node; } // The main function that first calls bintree2listUtil[], then follows // step 3 of the above algorithm function bintree2list[node] { // Base case if [node == null] return node; // Convert to DLL using bintree2listUtil[] node = bintree2listUtil[node]; // bintree2listUtil[] returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost node while [node.left != null] node = node.left; return node; } /* Function to print nodes in a given doubly linked list */ function printList[node] { while [node != null] { document.write[node.data + " "]; node = node.right; } } /* Driver program to test above functions */
// Let us create the tree shown in above diagram root = new Node[10]; root.left = new Node[12]; root.right = new Node[15]; root.left.left = new Node[25]; root.left.right = new Node[30]; root.right.left = new Node[36]; // Convert to DLL var head = bintree2list[root]; // Print the converted list printList[head]; // This code contributed by umadevi9616 |
Output
25 12 30 10 36 15
Another Approach:
Algorithm:
- Traverse the tree in inorder fashion.
- While visiting each node, keep track of DLL’s head and tail pointers, insert each visited node to the end of DLL using tail pointer.
- Return head of the list.
Below is the implementation of the above approach:
C++
|
// A C++ program for in-place // conversion of Binary Tree to DLL #include using namespace std; /* A binary tree node has data, and left and right pointers */ class node { public: int data; node* left; node* right; }; /* This is the core function to convert Tree to list.*/ void bintree2listUtil[node* root, node** head, node** tail] { if [root == NULL] return; bintree2listUtil[root->left, head, tail]; if [*head == NULL] { *head = root; } root->left = *tail; if [*tail != NULL] { [*tail]->right = root; } *tail = root; bintree2listUtil[root->right, head, tail]; } // The main function that first calls // bintree2listUtil[] node* bintree2list[node* root] { // Base case if [root == NULL] return root; node* head = NULL; node* tail = NULL; bintree2listUtil[root, &head, &tail]; return head; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode[int data] { node* new_node = new node[]; new_node->data = data; new_node->left = new_node->right = NULL; return [new_node]; } /* Function to print nodes in a given doubly linked list */ void printList[node* node] { while [node != NULL] { cout data right; } } /* Driver code*/ int main[] { // Let us create the tree shown in above diagram node* root = newNode[10]; root->left = newNode[12]; root->right = newNode[15]; root->left->left = newNode[25]; root->left->right = newNode[30]; root->right->left = newNode[36]; // Convert to DLL node* head = bintree2list[root]; // Print the converted list printList[head]; return 0; } // This code is contributed by rathbhupendra |
Java
|
// A Java program for in-place // conversion of Binary Tree to DLL import java.util.*; class GFG{ /* A binary tree node has data, and left and right pointers */ static class node { int data; node left; node right; }; /* * This is the core function to convert Tree to list. */ static node head, tail; static void bintree2listUtil[node root] { if [root == null] return ; node left = root.left; node right = root.right; bintree2listUtil[root.left]; if [head == null] { head = root; } root.left = tail; if [tail != null] { [tail].right = root; } tail = root; bintree2listUtil[root.right]; } // The main function that first calls // bintree2listUtil[] static void bintree2list[node root] {
// Base case if [root == null] head= root;
bintree2listUtil[root]; } /* Helper function that allocates a new node with the given data and null left and right pointers. */ static node newNode[int data] { node new_node = new node[]; new_node.data = data; new_node.left = new_node.right = null; return [new_node]; } /* Function to print nodes in a given doubly linked list */ static void printList[] { while [head != null] { System.out.print[head.data+ " "]; head = head.right; } } /* Driver code */ public static void main[String[] args] {
// Let us create the tree shown in above diagram node root = newNode[10]; root.left = newNode[12]; root.right = newNode[15]; root.left.left = newNode[25]; root.left.right = newNode[30]; root.right.left = newNode[36]; head = null; tail = null;
// Convert to DLL bintree2list[root]; // Print the converted list printList[]; } } // This code is contributed by umadevi9616 |
C#
|
// A C# program for in-place // conversion of Binary Tree to DLL using System; public class GFG { /* * A binary tree node has data, and left and right pointers */ public class node { public int data; public node left; public node right; }; /* * This is the core function to convert Tree to list. */ static node head, tail; static void bintree2listUtil[node root] { if [root == null] return; node left = root.left; node right = root.right; bintree2listUtil[root.left]; if [head == null] { head = root; } root.left = tail; if [tail != null] { [tail].right = root; } tail = root; bintree2listUtil[root.right]; } // The main function that first calls // bintree2listUtil[] static void bintree2list[node root] { // Base case if [root == null] head = root; bintree2listUtil[root]; } /* * Helper function that allocates a new node with the given data and null left * and right pointers. */ static node newNode[int data] { node new_node = new node[]; new_node.data = data; new_node.left = new_node.right = null; return [new_node]; } /* Function to print nodes in a given doubly linked list */ static void printList[] { while [head != null] { Console.Write[head.data + " "]; head = head.right; } } /* Driver code */ public static void Main[String[] args] { // Let us create the tree shown in above diagram node root = newNode[10]; root.left = newNode[12]; root.right = newNode[15]; root.left.left = newNode[25]; root.left.right = newNode[30]; root.right.left = newNode[36]; head = null; tail = null; // Convert to DLL bintree2list[root]; // Print the converted list printList[]; } } // This code is contributed by gauravrajput1 |
Javascript
|
// A javascript program for in-place // conversion of Binary Tree to DLL /* * A binary tree node has data, and left and right pointers */ class Node { constructor[] { this.data = 0; this.left = null; this.right = null; } } /* * This is the core function to convert Tree to list. */ var head, tail; function bintree2listUtil[root] { if [root == null] return; var left = root.left; var right = root.right; bintree2listUtil[root.left]; if [head == null] { head = root; } root.left = tail; if [tail != null] { [tail].right = root; } tail = root; bintree2listUtil[root.right]; } // The main function that first calls // bintree2listUtil[] function bintree2list[ root] { // Base case if [root == null] head = root; bintree2listUtil[root]; } /* * Helper function that allocates a new node with the given data and null left * and right pointers. */ function newNode[data] { var new_node = new Node[]; new_node.data = data; new_node.left = new_node.right = null; return [new_node]; } /* Function to print nodes in a given doubly linked list */ function printList[] { while [head != null] { document.write[head.data + " "]; head = head.right; } } /* Driver code */
// Let us create the tree shown in above diagram var root = newNode[10]; root.left = newNode[12]; root.right = newNode[15]; root.left.left = newNode[25]; root.left.right = newNode[30]; root.right.left = newNode[36]; head = null; tail = null; // Convert to DLL bintree2list[root]; // Print the converted list printList[]; // This code is contributed by gauravrajput1 |
Output 25 12 30 10 36 15
This article is compiled by Ashish Mangla and reviewed by GeeksforGeeks team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
You may also like to see Convert a given Binary Tree to Doubly Linked List | Set 2 for another simple and efficient solution.
Article Tags :
Linked List
Tree
Amazon
doubly linked list
Goldman Sachs
Microsoft
Practice Tags :
Amazon
Microsoft
Goldman Sachs
Linked List
Tree
Read Full Article
1. Using Inorder Traversal
The idea is to perform an inorder traversal on the tree, and for every node encountered, insert it at the beginning of a doubly linked list. Since we are inserting nodes at the beginning of the doubly linked list, reverse the linked list to follow the same order of nodes as in the inorder traversal.
Following is the implementation in C++, Java, and Python based on the above idea:
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 | #include 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; } }; // Helper function to print a given doubly linked list void printDLL[Node* &head] { Node* curr = head; while [curr != nullptr] { cout left = nullptr; // store right child Node* right = root->right; // insert the current node at the beginning of a doubly linked list root->right = head; if [head != nullptr] { head->left = root; } head = root; // recursively convert the right subtree convert[right, head]; } // Function to reverse a doubly-linked list void reverse[Node*& head] { Node* prev = nullptr; Node* current = head; while [current] { swap[current->left, current->right]; prev = current; current = current->left; } if [prev != nullptr] { head = prev; } } // The main function to in-place convert a given binary tree into a // doubly linked list void convert[Node* root] { // head of the doubly linked list Node* head = nullptr; // convert the above binary tree into doubly linked list convert[root, head]; // reverse the linked list reverse[head]; // print the list printDLL[head]; } int main[] { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 */ 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]; convert[root]; return 0; } |
DownloadRun Code
Output:
4 2 5 1 6 3 7
Introduction
Binary Trees are a type of data structure where each data is stored as a node, and each node has two child nodes. The three primary traversal techniques are pre-order, in-order, and post-order.
Linked Lists are another type of data structure where data is stored in nodes, and each node is connected via links. A linked list can be singly linked or doubly-linked depending upon the number of links. The two pointers in a doubly-linked list are: next and previous.
In this article, we will learn to convert a given binary tree into a doubly-linked list by performing in-order traversal. To know more about the various tree traversals, click hereTree Traversals.
Q. Program to convert a given binary tree to doubly linked list.
Explanation
In this program, we need to convert the given binary tree to corresponding doubly liked list.
The binary tree is a tree data structure in which each node has at most two children node.
This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node. Traverse left sub-tree and convert it into the doubly linked list by adding nodes to the end of the list. In this way, leftmost node will become head of the list. Then, convert the right sub-tree into the doubly linked list.
Binary tree:
Corresponding doubly linked list:
Algorithm
- Define a Node class which represents a node in the binary tree. It will have three properties: data left, and right where the left and right represent two children of a node.
- Root will represent the root of the binary tree. Head and tail node represent the head and tail of the doubly linked list.
- BinaryTreeToDLL[] will convert the given binary tree to corresponding doubly linked list.
- Perform inorder traversal of the binary tree by converting the left subtree first.
- If the list is empty, both head and tail will point to a node.
- If the list is not empty, the node will be inserted at the end of the list. Here, pointer left, and right will represent the previous and next pointer of the doubly linked list.
- Now, recursively call BinaryTreeToDLL[] to convert the right subtree.
- display[] will show all the nodes present in the list.
- Define a new node 'current' that will point to the head.
- Print current.data till current points to null.
- Current will point to the next node in the list in each iteration.
C++
// C++ program to convert a given Binary // Tree to Doubly Linked List #include #include // Structure for tree and linked list struct Node { int data; Node *left, *right; }; // A simple recursive function to convert a given // Binary tree to Doubly Linked List // root --> Root of Binary Tree // head_ref --> Pointer to head node of created // doubly linked list void BToDLL[Node* root, Node** head_ref] { // Base cases if [root == NULL] return; // Recursively convert right subtree BToDLL[root->right, head_ref]; // insert root into DLL root->right = *head_ref; // Change left pointer of previous head if [*head_ref != NULL] [*head_ref]->left = root; // Change head of Doubly linked list *head_ref = root; // Recursively convert left subtree BToDLL[root->left, head_ref]; } // Utility function for allocating node for Binary // Tree. Node* newNode[int data] { Node* node =new Node; node->data = data; node->left = node->right = NULL; return node; } // Utility function for printing double linked list. void printList[Node* head] { printf["Extracted Double Linked list is: "]; while [head] { printf["%d ", head->data]; head = head->right; } } // Driver program to test above function int main[] { /* Constructing below tree 5 / 3 6 / 1 4 8 / / 0 2 7 9 */ Node* root = newNode[5]; root->left = newNode[3]; root->right = newNode[6]; root->left->left = newNode[1]; root->left->right = newNode[4]; root->right->right = newNode[8]; root->left->left->left = newNode[0]; root->left->left->right = newNode[2]; root->right->right->left = newNode[7]; root->right->right->right = newNode[9]; Node* head = NULL; BToDLL[root, &head]; printList[head]; return 0; } |