0

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

i am talking about function "flatten", I know i can do it without making another function named help but I want to do this question this way. The help function is flattening the tree correctly and returning it correctly in TreeNode* ans, but it is not reflecting in root, in root it is printing from original

using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int val) {
        this->val = val;
        left = right = nullptr;
    }
};

TreeNode *takeInput() {
    int rootData;
    cout << "Enter data of root node" << endl;
    cin >> rootData;
    if (rootData == -1) {
        return nullptr;
    }
    TreeNode *root = new TreeNode(rootData);

    queue<TreeNode *> pendingNodes;
    pendingNodes.push(root);

    while (!pendingNodes.empty()) {
        TreeNode *front = pendingNodes.front();
        pendingNodes.pop();

        int leftNodeData;
        cout << "Enter val of left child of parent " << front->val << endl;
        cin >> leftNodeData;
        if (leftNodeData != -1) {
            front->left = new TreeNode(leftNodeData);
            pendingNodes.push(front->left);
        }

        int RightNodeData;
        cout << "Enter val of Right child of parent " << front->val << endl;
        cin >> RightNodeData;
        if (RightNodeData != -1) {
            front->right = new TreeNode(RightNodeData);
            pendingNodes.push(front->right);
        }
    }
    return root;
}

void print(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode *> pendingNodes;
    pendingNodes.push(root);

    while (!pendingNodes.empty()) {
        TreeNode *front = pendingNodes.front();
        pendingNodes.pop();

        cout << front->val << ":";

        if (front->left != nullptr) {
            cout << " L: " << front->left->val;
            pendingNodes.push(front->left);
        }

        if (front->right != nullptr) {
            cout << " R: " << front->right->val;
            pendingNodes.push(front->right);
        }
        cout << endl;
    }
}

TreeNode *help(TreeNode *root) {
    if (root == nullptr) {
        return nullptr;
    }

    TreeNode *leftAns = help(root->left);
    TreeNode *rightAns = help(root->right);
    if (leftAns != nullptr) {
        TreeNode *temp = leftAns;
        while (temp->right != nullptr) {
            temp = temp->right;
        }
        temp->right = root;
        root->left = nullptr;
    }
    root->right = rightAns;
    if (leftAns != nullptr) {
        root = leftAns;
        return leftAns;
    }
    return root;
}

void flatten(TreeNode *root) {
    TreeNode *ans = help(root);
    // help(root);
    // *root = *ans;
    root = ans;

    // root = help(root);
}

int main() {
    TreeNode *root = takeInput();
    print(root);
    flatten(root);
    cout << "ans:" << endl;
    print(root);
    return 0;
}```
Ayush Singhal
  • 1
  • 1
  • 3
    Because you are passing `root` to `flatten()` by value instead of by reference. – user207421 May 15 '22 at 05:24
  • @alexpdev root= &ans is not working, it is saying a value of type "TreeNode **" cannot be assigned to an entity of type "TreeNode *" – Ayush Singhal May 15 '22 at 06:00
  • It turns out that you are solving the wrong problem. The challenge wants you to output preorder, but you are trying to output inorder, moving the root to the position between left and right sublists. The answer you are trying to produce is leftAnswer->root->rightAnswer. For preorder, *the root should not move or change*, the answer is root->leftAnswer->rightAnswer, so pass by reference is not needed at all. – n. 1.8e9-where's-my-share m. May 15 '22 at 18:50

1 Answers1

0

As user207421 stated in his comment, you are currently passing root into the flatten function by value meaning that when root is assigned the value of ans in the line

root = ans;

Only the local copy of root is being altered. If you passed root into the function by reference, the value of the root value would be changed rather than just a local copy.

The function would simply need to be changed to

void flatten(TreeNode *&root) {
    root = help(root);
}

Edit:

Having looked over the leet code link I now realize the previous answer is invalid for doesn't exactly match the provided flatten function signature given in the challenge. I will leave the original answer above in case it is useful. If you wish to change the value of root, you should assign the value pointed to by answer to the memory location pointed to be root

void flatten(TreeNode *root) {
    *root = *help(root);
}
Kallen Murphy
  • 124
  • 4