Flattening Trees

 

// Flatten a Binary Tree in pre order fashion:

// left to NULL and right to next value:

void help(TreeNode* root, TreeNode* &tmp){

    if(!root) return;

    tmp->left = NULL;

    tmp->right = root;

    tmp = root;

    TreeNode* l = root->left;

    TreeNode* r = root->right;

    // call for others:

    help(l, tmp);

    help(r, tmp);

    return;

 

}

void flatten(TreeNode* root){

    TreeNode* dummy = new TreeNode(-1);

    TreeNode* tmp = dummy;

    help(root, tmp);

    tmp->left = tmp->right = 0;

    return;

}

// Flatten a Binary Search Tree into Linked List in sorted manner:

//left as null and right as next pointer

void help(TreeNode* root, TreeNode* &tmp){

    if(root == 0) return;

    help(root->left, tmp);

    tmp->left = NULL;

    tmp->right = root;

    tmp = root;

    help(root->right, tmp);

}

void flattenBst(TreeNode* root){

    TreeNode* dummy = new TreeNode(-1);

    TreeNode* tmp = dummy;

    help(root, tmp);

    tmp->left = tmp->right = 0;

    return;

}