Solution: Flatten Binary Tree to Linked List
Tags: algorithms, javascript, java, python
Published: 2021-05-14 08:49:02

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/1207642).*

---

#### [Leetcode Problem #114 (*Medium*): Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|root = [1,2,5,3,4,null,6]
Output:|[1,null,2,null,3,null,4,null,5,null,6]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg)
>
Example 2:||
|---:|---|
Input:|root = []
Output:|[]
>
Example 3:||
|---:|---|
Input:|root = [0]
Output:|[0]

---

#### ***Constraints:***
>
 - The number of nodes in the tree is in the range `[0, 2000]`.
 - `-100 <= Node.val <= 100`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

***Morris Traversal (O(1) Space, O(N) Time) Approach:***

There _is_ actually a way to traverse a binary tree with a **space complexity** of **O(1)** while staying at a **time complexity** of **O(N)**, though it does require modifying the tree's structure. In this problem that's specifically being called for, so it's a valid approach, though it won't always be appropriate to modify the source binary tree in other situations.

The approach is called the **Morris traversal**. At its heart, it takes advantage of the basic nature of ordered traversals to iterate through and unwind the tree. In a **pre-order traversal** of a binary tree, each vertex is processed in **(node, left, right)** order. This means that the entire left subtree could be placed between the node and its right subtree.

To do this, however, we'll first have to locate the last node in the left subtree. This is easy enough, since we know that the last node of a pre-order tree can be found by moving right as many times as possible from its root.

So we should be able to move through the binary tree, keeping track of the curent node (**curr**). Whenever we find a left subtree, we can dispatch a **runner** to find its last node, then stitch together both ends of the left subtree into the right path of **curr**, taking heed to sever the left connection at **curr**.

Once that's done, we can continue to move **curr** to the right, looking for the next left subtree. When **curr** can no longer move right, the tree will be successfully flattened.

![Morris Traversal Visual](https://i.imgur.com/sqnrz9m.gif)

 - _**Time Complexity: O(N)** where **N** is the number of **nodes** in the binary tree_
 - _**Space Complexity: O(1)**_

---

***O(1) Space Approach:***

In order to properly connect the **linked list**, we'll need to start at the bottom and work up. This means that we'll need to move in _reverse_ **pre-order traversal** order through the **binary tree**. Since pre-order traversal is normally **(node, left, right)**, we'll have to move in the reverse order of **(right, left, node)**.

In order to complete this solution in **O(1) space**, we won't be able to conveniently backtrack via a **stack**, so the key to this solution will be to retreat all the way back up to the **root** each time we reach a leaf. This will push the **time complexity** to **O(N^2)**.

We'll want to first set up **head** and **curr** to keep track of the head of the linked list we're building and the current node we're visiting. We'll know we're finished once **head = root**.

To follow the reverse pre-order traversal order, we'll first attempt to go right and then left. Since we're backtracking to **root**, however, we'll eventually run back into the same node that we've set as **head** doing this. To prevent this, we'll stop _before_ moving to the **head** node and sever the connection.

Now that we can't run into already-completed territory, we can be confident that any leaf we move to must be the next value for **head**, so we should connect it to the old **head**, update **head**, and reset back to the **root**.

As noted before, once **head = root**, we've finished our traversal and can exit the function.

 - _**Time Complexity: O(N^2)** where **N** is the number of **nodes** in the binary tree, due to repeated backtracking to root_
 - _**Space Complexity: O(1)**_

---

***Recursive Approach:***


In order to properly connect the **linked list**, we'll need to start at the bottom and work up. This means that we'll need to move in _reverse_ **pre-order traversal** order through the **binary tree**. Since pre-order traversal is normally **(node, left, right)**, we'll have to move in the reverse order of **(right, left, node)**.

Binary tree traversal is prime ground for a **recursive** solution, so let's define a helper (**revPreOrder**) for the purpose. We'll also keep a global variable **head** to keep track of the head of the linked list as we work our way backwards.

Per our reverse pre-order traversal approach, we want to recursively work down the right path first then the left path, if they exist. Once we've flattened the left and right paths recursively, **head** should at this point be equal to the next node after the current one, so we should set it as **node.right**. We shouldn't forget to set **node.left** to **null**, as well.

Once we're done with the current node, we can update **head** to **node** and allow the recursion to complete and move back up to the next layer. Once the recursion stack is exhausted, **head** will be equal to **root** again.

Lastly, we have to deal with an edge case of an empty **root**, so we can just make sure to only call the initial recursion on **root** if **root** actually is a node. There is no need for a **return** statement, because the test suite will evaluate **root** directly.

 - _**Time Complexity: O(N)** where **N** is the number of **nodes** in the binary tree_
 - _**Space Complexity: O(N)** for the **recursion stack**, which is as long as the maximum depth of the binary tree, which can go up to **N**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Morris Traversal:***
```javascript
var flatten = function(root) {
    let curr = root
    while (curr) {
        if (curr.left) {
            let runner = curr.left
            while (runner.right) runner = runner.right
            runner.right = curr.right, curr.right = curr.left, curr.left = null
        }
        curr = curr.right
    }
};
```

##### ***w/ O(1) Space:***
```javascript
var flatten = function(root) {
    let head = null, curr = root
    while (head != root) {
        if (curr.right === head) curr.right = null
        if (curr.left === head) curr.left = null
        if (curr.right) curr = curr.right
        else if (curr.left) curr = curr.left
        else curr.right = head, head = curr, curr = root
    }
};
```

##### ***w/ Recursion:***
```javascript
var flatten = function(root) {
    let head = null
    const revPreOrder = node => {
        if (node.right) revPreOrder(node.right)
        if (node.left) revPreOrder(node.left)
        node.left = null, node.right = head, head = node
    }
    if (root) revPreOrder(root)
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Morris Traversal:***
```python
class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                runner = curr.left
                while runner.right: runner = runner.right
                runner.right, curr.right, curr.left = curr.right, curr.left, None
            curr = curr.right
```

##### ***w/ O(1) Space:***
```python
class Solution:
    def flatten(self, root: TreeNode) -> None:
        head, curr = None, root
        while head != root:
            if curr.right == head: curr.right = None
            if curr.left == head: curr.left = None
            if curr.right: curr = curr.right
            elif curr.left: curr = curr.left
            else: curr.right, head, curr = head, curr, root
```

##### ***w/ Recursion:***
```python
class Solution:
    head = None
    def flatten(self, root: TreeNode) -> None:
        def revPreOrder(node: TreeNode) -> None:
            if node.right: revPreOrder(node.right)
            if node.left: revPreOrder(node.left)
            node.left, node.right, self.head = None, self.head, node
        if root: revPreOrder(root)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Morris Traversal:***
```java
class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode runner = curr.left;
                while (runner.right != null) runner = runner.right;
                runner.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
}
```

##### ***w/ O(1) Space:***
```java
class Solution {
    public void flatten(TreeNode root) {
        TreeNode head = null, curr = root;
        while (head != root) {
            if (curr.right == head) curr.right = null;
            if (curr.left == head) curr.left = null;
            if (curr.right != null) curr = curr.right;
            else if (curr.left != null) curr = curr.left;
            else {
                curr.right = head;
                head = curr;
                curr = root;
            }
        }
    }
}
```

##### ***w/ Recursion:***
```java
class Solution {
    TreeNode head = null;
    public void flatten(TreeNode root) {
        if (root != null) revPreOrder(root);
    }
    private void revPreOrder(TreeNode node) {
        if (node.right != null) revPreOrder(node.right);
        if (node.left != null) revPreOrder(node.left);
        node.left = null;
        node.right = head;
        head = node;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Morris Traversal:***
```c++
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                TreeNode* runner = curr->left;
                while (runner->right != nullptr) runner = runner->right;
                runner->right = curr->right, curr->right = curr->left, curr->left = nullptr;
            }
            curr = curr->right;
        }
    }
};
```

##### ***w/ O(1) Space:***
```c++
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *head = nullptr, *curr = root;
        while (head != root) {
            if (curr->right == head) curr->right = nullptr;
            if (curr->left == head) curr->left = nullptr;
            if (curr->right) curr = curr->right;
            else if (curr->left) curr = curr->left;
            else curr->right = head, head = curr, curr = root;
        }
    }
};
```

##### ***w/ Recursion:***
```c++
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root) revPreOrder(root);
    }
private:
    TreeNode* head = nullptr;
    void revPreOrder(TreeNode* node) {
        if (node->right) revPreOrder(node->right);
        if (node->left) revPreOrder(node->left);
        node->left = nullptr, node->right = head, head = node;
    }
};
```