CODEWITHSUNDEEP
pointersbinary-treepass-by-referencedoubly-linked-listpass-by-value
Yash Meshram
Yash Meshram

Reputation: 1

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   3

The 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 have doubt regarding root. The root pointer works with passing by value and does not works when it is passed by reference.

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?

Upvotes: 0

Views: 157

Answers (1)

mitch_
mitch_

Reputation: 1436

At first glance, one problem is the API of inorder itself. You are assigning nroot = root; to see why this is a problem, consider this simpler example:

void set_x(int *x, int *y)
{
  x = y;
}

Remember that pointers are really just memory addresses. So, the assignment of x = y says, "replace the memory address that x contains, and set it to whatever y contains". At no stage do you actually change the value at the memory address.

Now, considering nroot = root again, here you are just giving the local variable you have a new memory address, but not updating anything. So at your call side BTtoDLL, you provide it nullptr for the address, to which it never uses it, and never sets it. So, BTtoDLL will never see any change to nroot.

Upvotes: 0

Related Questions