Write a function that inserts the nodes of a binary tree into an ordered linked

Question

Write a function that inserts the nodes of a binary tree into an ordered linked list. Also write a program to test your function.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.