114. Flatten Binary Tree to Linked List 🚀
Tags: javascript, tutorial, beginners, leetcode
Published: 2022-05-09 18:47:27

### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

![image](https://assets.leetcode.com/users/images/5bc76c1a-bfc7-4a41-914c-91907dc2bcd1_1652112176.8678908.gif)

## The Question
For this article we will be covering Leetcode's '[114. Flatten Binary Tree to Linked List](https://leetcode.com/problems/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:

>![Example](https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg)

```
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](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [Post Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Post-order)
4. [Pre Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order)
5. [Linked List](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Tree_traversal#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](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) could do this problem in ***O(1) space complexity***. But [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#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

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/696216921/)


***

# 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;
};


```