114. Flatten Binary Tree to Linked List 🚀

Solution Developed In:

The Question

For this article we will be covering Leetcode's '114. Flatten Binary Tree to Linked List' question.

Question:

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]

Explaining The Question

This Question is rated Medium. Which I believe is accurate. Figuring this question out in O(n) space is fairly straightforward. Perform pre-order traversal and send the nodes to a new list. For this question, we're going to be modifying the tree in-place.

What we're being asked is turn a binary tree into a linked list and do it so that the Linked List appears to be a binary tree traversed in pre-order.

Now this may seem difficult at first, but it's actually pretty simple. So long as you understand the concepts below.

Recommended Knowledge

1. Binary Tree
2. Depth First Search
3. Post Order Traversal
4. Pre Order Traversal
5. Linked List

What do we know?

1. We have a binary tree (Most times, it could be empty)
2. We need to flatten the tree into a linked list
3. We need to traverse the tree in post order to achieve this for O(h) space
4. We need to move the left tree into the right tree of the current node

How we're going to do it:

We're going to be doing a post order traversal. Because we want to move the entire left tree of the current node into the right tree of the current node. With the end of that left tree pointing to the current right node. It sounds confusing, but don't worry it will make sense.

1. Use post_order_traversal to get the nodes in post order
2. Keep traversing the nodes in post order until we find a node that has a left node.
3. Once we have detected that left node we're going to initialise a new pointer called lefts_right_most_node. His job is to find the root.left further right node. We're going to use a while loop to keep getting the right nodes until we find it. The reason we do this is because the furthest right node will be used to connect the bottom of that sub tree to the current right node. We do this because, we're going to merge the 2 sub trees into one.
4. Once we have found the lefts_right_most_node we're going to connect the lefts_right_most_node to the current right node.
5. We then overwrite the right node of the current node with the lefts_right_most_node. This works because the last node in the left tree connects to the current right node. So it's inserting the entire left tree into the right tree but before all the elements in the right tree.
6. We then erase the left node of the current node. This is because we've already moved the left tree into the right tree, so we don't need to keep reference to it anymore.
7. We continually do this until we reach the end of the post order traversal.

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes in our Binary Tree | As we're going to traverse all of the nodes within the tree.

• Space Complexity: O(h) | Where h is the height of nodes in our Call Stack | As we're using a recursive call stack to traverse the tree.

'Could this be improved?' Yes! Morris Traversal could do this problem in O(1) space complexity. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.

Leetcode Results:

See Submission Link:

• Runtime: 56 ms, faster than 99.88% of JavaScript online submissions for Flatten Binary Tree to Linked List
• Memory Usage: 44.1MB, less than 90.67% of JavaScript online submissions for Flatten Binary Tree to Linked List

---

The Solution

var flatten = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                   114. Flatten Binary Tree to Linked List                  */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    // So, we're not going to traverse the tree in pre-order traversal.
    // Instead, we're going to do the opposite of what we was just asked to do.
    // The reason for this is we're optimising for space complexity. If we did pre-order
    // traversal, we would have to store an entirely new tree in memory. While in this solution, we only store
    // the height of the tree in memory.

    // Do Post Order Traversal

    // Base case, empty node
    if (!root) {
        return null;
    }

    flatten(root.left);
    flatten(root.right);

    // Now, we're at the left most node,
    // We're going to ask if this current node
    // even has a left node?
    // If it does, move it's entire left sub tree
    // into the right tree but in-order. :D

    // Move the left tree to the right tree
    if (root.left) {
        // So, we're going to get the current left nodes
        // right most node. Because we're going to set this nodes
        // pointer to be the right node of the current node.
        let lefts_right_most_node = root.left;

        // Get me the left's right most node
        while (lefts_right_most_node.right) {
            lefts_right_most_node = lefts_right_most_node.right;
        }

        // Adjust the right most nodes pointer
        // to point to the current nodes right node
        lefts_right_most_node.right = root.right;

        // Add the left tree into the right tree.
        root.right = root.left;

        // Remove the left tree. We don't need it anymore.
        root.left = null;
    }

    return root;
};