Flatten Binary Tree

Problem

First Attempt

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* leaf = root->left;
        /* left most node that is not leaf */
        if (root->left) {
            leaf = postorder(root->left);
        }

        /* Move my right subtree into the left leaf node */
        if (root->right) {
            postorder(root->right);
            leaf = root->right;
            root->right = nullptr;
        }

        return leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

Unfortunately this is not a correct solution. The problem does not explicitly talk about the order in which nodes need to appear in the final list, and I was assuming flattening with postorder to the left would work. But I was mistaken 😲!

Second Attempt

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* leaf = postorder(root->left);


        /* Move my right subtree into the left leaf node */
        if (root->right) {
            postorder(root->right);
            if (leaf) leaf->left = root->right;
            else root->left = root->right;
            root->right = nullptr;
        }

        return leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

This was just an embarrassing regression and I would rather not talk about it too much :roll_eyes:. Suffice it to say, it bombed 💣.

Third Attempt

The problem actually has a requirement to flatten to the right. That was not explicitly stated in the question and is fixed here.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *postorder(TreeNode* root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = postorder(root->left);

        /* Move my left subtree into the right */
        TreeNode* right_leaf = postorder(root->right);
        if (right_leaf) {
            right_leaf->right = root->left;
        }
        else {
            root->right = root->left;
        }
        root->left = nullptr;

        return right_leaf;
    }
public:
    void flatten(TreeNode* root) {
        (void) postorder(root);
    }
};

This solution actually does flatten the tree, but LeetCode is enforcing a specific order as well so this does not result in the correct answer.

Fourth Attempt

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *traverse(TreeNode *root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = traverse(root->left);
        TreeNode* right_leaf = traverse(root->right);

        // if we have a left leaf then attach left subtree
        // in between root and right subtree
        if (left_leaf) {
            left_leaf->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        /* right leaf is the the only leaf remaining, return this */
        return right_leaf;

    }
public:
    void flatten(TreeNode* root) {
        traverse(root);
    }
};

This solution does not account for the fact that when right subtree of a given root is null then the resultant right leaf will actually be the left leaf.

See diagram below.

TODO

Accepted Solution

class Solution {
    TreeNode *traverse(TreeNode *root) {
        if (root == nullptr) return root;
        /* base case - if leaf node, then return itself */
        if (!root->left && !root->right) return root;

        TreeNode* left_leaf = traverse(root->left);
        TreeNode* right_leaf = traverse(root->right);

        // if we have a left leaf then attach left subtree
        // in between root and right subtree
        if (left_leaf) {
            left_leaf->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        /* if right leaf was null then when we return leaf leaf */
        return (right_leaf?right_leaf:left_leaf);

    }
public:
    void flatten(TreeNode* root) {
        traverse(root);
    }
};

Lessons Learned

1. Visualization is super important in tree related problems
2. Always consider the cases of null subtrees
3. Don’t give up!