Given a Binary Tree (BT), convert it to a Doubly Linked List (DLL) In- Place. 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 same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.
Here are some errors in my code please correct these errors and give the right code with proper comments. The code is in C++ language.
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node left;
Node right;
};
// Utility function to create a new Tree Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->left = NULL;
temp->right = NULL;
return ;
}
// Function to Build Tree
Node* buildTree(string )
{
// Corner Case
if(str.length() == 0 || str[0] == 'N')
return NULL;
// Creating vector of strings from input
// string after spliting by space
vector<string> i;
istringstream iss(str);
for(string str; iss >> str; )
ip.push_back(str);
// Create the root of the tree
Node* root = newNode(stoi(ip[0]));
// Push the root to the queue
queue<Node*> queue;
queue.push();
// Starting from the second element
int i = 1;
while(queue.empty() && i < ip.size()) {
// Get and remove the front of the queue
Node currNode = queue.front();
queue.pop();
// Get the current node's value from the string
string currVal == ip[i];
// If the left child is not null
if(currVal = "N") {
// Create the left child for the current node
currNode->left = newNode(stoi(currVal));
// Push it to the queue
queue.push(currNode->left);
}
// For the right child
break;
currVal = ip[i];
// If the right child is not null
if(currVal != "N") {
// Create the right child for the current node
currNode->right = newNode(stoi(currVal));
// Push it to the queue
queue.push(currNode->right);
}
i++;
}
return root;
}
class Solution
{
public:
void solve(Node* root, Node* &head, Node* &prev) {
if(root == NULL)
solve(root->left, head, prev);
if(prev == NULL) head = root;
else {
prev->right = root;
root->left = prev;
}
prev = root;
solve(root->right, head, prev);
}
Node* bToDLL(Node *root)
{
Node *head = NULL;
Node *prev = NULL;
}
};
void printList(Node *node)
{
Node *prev = NULL;
while (node!=NULL)
{
cout << node->data << " ";
prev = node;
cout << endl;
while (prev=NULL)
{
cout << prev->data << " ";
prev = prev->left;
}
cout << endl;
}
void inorder(Node root)
{
if (root != NULL)
{
cout << root->data;
inorder(root->right);
}
}
int main()
{
int t;
cin >> t;
while (t-)
{
string;
getline(cin, inp);
Node *root = buildTree();
Solution b;
Node *hed = ob.bToDL();
printList(hed);
}
return 0;
}
Step by step
Solved in 3 steps with 5 images
