Convert A Given Binary Tree To Doubly Linked List
The problem statement is:
Given a Binary Tree, convert this binary tree to a Doubly Linked List. A Binary Tree (BT) is a data structure in which each node has at most two children. A Doubly Linked List contains a previous pointer, along with the next pointer and data. The order of nodes in Doubly Linked List must be the same as Inorder of the given Binary Tree. The doubly linked list should be returned by taking the next pointer as right and the previous pointer as left.
You need to return the head of the Doubly Linked List.
For example:
4 / \ 2 5 / \ 1 3The doubly linked list would be: 1 2 3 4 5
My code is:
class BinaryTreeNode
{
public :
T data;
BinaryTreeNode<T> *left;
BinaryTreeNode<T> *right;
BinaryTreeNode(T data) {
this -> data = data;
left = NULL;
right = NULL;
}
};
void inorder(BinaryTreeNode<int>* root,BinaryTreeNode<int>* prev,BinaryTreeNode<int>* nroot){
if(!root) return;
inorder(root->left,prev,nroot);
if(prev == NULL) nroot=root;
else{
root->left = prev;
prev->right=root;
}
prev=root;
inorder(root->right,prev,nroot);
}
BinaryTreeNode<int>* BTtoDLL(BinaryTreeNode<int>* root) {
BinaryTreeNode<int>* prev=NULL;
BinaryTreeNode<int>* nroot=NULL;
inorder(root,prev,nroot);
return nroot;
}
I am not getting any output for the above code. I am not able to find what is wrong with the above code.
Edit:
I need to pass the pointers prev and nroot by reference. Now I have another doubt regarding root. The root pointer works with passing by value and does not works when it is passed by reference.
This code works:
void inorder(BinaryTreeNode<int>* root,BinaryTreeNode<int>*& prev,BinaryTreeNode<int>* &nroot){
if(!root) return;
inorder(root->left,prev,nroot);
if(prev == NULL) nroot=root;
else {
root->left = prev;
prev->right=root;
}
prev=root;
inorder(root->right,prev,nroot);
}
But when root is passed by reference, it does not work.
void inorder(BinaryTreeNode<int>*& root,BinaryTreeNode<int>*& prev,BinaryTreeNode<int>* &nroot){
if(!root) return;
inorder(root->left,prev,nroot);
if(prev == NULL) nroot=root;
else{
root->left = prev;
prev->right=root;
}
prev=root;
inorder(root->right,prev,nroot);
}
How can I know which variable should be passed by reference and which variable should by passed by value with regard to pointers?
Comments
Post a Comment