LeetCode: 114. Flatten Binary Tree to Linked List

The Problem

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

void flatten(TreeNode* root) {
    vector<short> preorder;
    flattenHelper(root, preorder);

    TreeNode *&head = root;
    for(int i = 1; i < preorder.size(); ++i){

        if(head->right == NULL) {
	        head->right = new TreeNode(preorder[i]);
        }else {
	        head->right->val = preorder[i];
        }

        head->left = NULL;
        head = head->right; 
    }
}

void flattenHelper(TreeNode* root, vector<short> &preorder) {
    if (root == NULL) return;
    preorder.push_back((short)root->val);
    flattenHelper(root->left, preorder);
    flattenHelper(root->right, preorder);
}

Here's an explanation of the code:

1. void flatten(TreeNode* &root): This is the main function for flattening the binary tree. It takes a reference to a pointer to a TreeNode as an argument, which allows the function to modify the root of the tree if necessary.

2. vector<short> preorder;: This vector will be used to store the values of the tree nodes in pre-order traversal order.

3. flattenHelper(root, preorder);: This line calls the flattenHelper function to perform a pre-order traversal of the binary tree and populate the preorder vector with the values of the nodes.

4. TreeNode *&head = root;: This line declares a reference to a pointer to a TreeNode named head and initializes it with the same value as the root pointer. The reference allows us to update the root pointer as we build the flattened linked list.

5. The for loop iterates through the preorder vector starting from index 1 (skipping the root node, as it's already the head of the flattened list).

6. Inside the loop:

• If head->right is NULL, it means that there's no right child node in the flattened list yet. In this case, a new TreeNode is created with the value from the preorder vector, and it's assigned as the right child of the current head.
• If head->right is not NULL, it means that the right child node already exists, so its value is updated with the value from the preorder vector.
• head->left is set to NULL because we are building a singly linked list.
• head is updated to head->right, moving to the next node in the flattened list.

7. void flattenHelper(TreeNode* root, vector<short> &preorder): This is a recursive helper function that performs a pre-order traversal of the binary tree.

• If root is NULL, the function returns early.
• Otherwise, the value of the current node (root->val) is added to the preorder vector.
• The function then recursively calls itself on the left and right subtrees of the current node.