# How To Reset The Global Variable Prev?

## 01 August 2020 - 1 answer

This is the C solution for Leetcode 114. Flatten Binary Tree to Linked List

``````struct TreeNode* prev = NULL;

void flatten(struct TreeNode* root){
if (root == NULL){
return;
}
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root;
}
``````

When tested with

``````[1,2,5,3,4,null,6]
[0]
``````

It would have this error output

``````[1,null,2,null,3,null,4,null,5,null,6]
[0,null,1,null,2,null,3,null,4,null,5,null,6]
``````

The correct output should be

``````[1,null,2,null,3,null,4,null,5,null,6]
[0]
``````

But if tested individually, both cases can pass, this is because the prev is a global variable.So how to reset this value?

Here is an iterative solution, if you'd be interested:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/

void flatten(struct TreeNode* root) {
struct TreeNode* lr;

while (root != NULL) {
if (root->left != NULL) {
lr = root->left;

while (lr->right != NULL) {
lr = lr->right;
}

lr->right = root->right;
root->right = root->left;
root->left = NULL;
}

root = root->right;
}
}
``````

And here is LeetCode's recursive solution in Java with comments:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

private TreeNode flattenTree(TreeNode node) {

// Handle the null scenario
if (node == null) {
return null;
}

// For a leaf node, we simply return the
// node as is.
if (node.left == null && node.right == null) {
return node;
}

//Recursively flatten the left subtree
TreeNode leftTail = this.flattenTree(node.left);

// Recursively flatten the right subtree
TreeNode rightTail = this.flattenTree(node.right);

// If there was a left subtree, we shuffle the connections
// around so that there is nothing on the left side
// anymore.
if (leftTail != null) {
leftTail.right = node.right;
node.right = node.left;
node.left = null;
}

// We need to return the "rightmost" node after we are
// done wiring the new connections.
return rightTail == null ? leftTail : rightTail;
}

public void flatten(TreeNode root) {

this.flattenTree(root);
}
}
``````

## References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.