1. Introduction

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

1. 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.
2. The “linked list” should be in the same order as a Preorder traversal of the binary tree.

2. Content

I will discuss how to convert a binary tree to a linked list using Preorder traversal.

Below are a few articles you can read on Preorder Traversal:

1. Preorder using Recursion and Iteration
2. Preorder Iterator

Example:

3. Flatten the Binary Tree to LinkedList.

1. First, handle the basic condition

public void flatten(TreeNode root) {
        if(root == null) return;
}

2. Do Preorder traversal

public void flatten(TreeNode root) {
    if(root == null) return;
        
    List<TreeNode> list = new ArrayList<>();
    preorder(root, list);
}
    
private void preorder(TreeNode root, List<TreeNode> preorder) {
    if(root != null) {
        preorder.add(root);
        preorder(root.left, preorder);
        preorder(root.right, preorder);
    }
}

3. Link the nodes by making the left node as null and right node as the next element in Preorder traversal.

Entire Implementation:

public void flatten(TreeNode root) {
    if(root == null) return;
        
    List<TreeNode> list = new ArrayList<>();
    preorder(root, list);
        
    TreeNode newRoot = root;
    for(int i = 1; i < list.size(); i++) {
        newRoot.left = null;
        newRoot.right =  list.get(i);
        newRoot = newRoot.right;
    }
}
    
private void preorder(TreeNode root, List<TreeNode> preorder) {
    if(root != null) {
        preorder.add(root);
        preorder(root.left, preorder);
        preorder(root.right, preorder);
    }
}

Time Complexity: O(n) as we traverse all nodes exactly once.

Space Complexity: O(n) as we save all nodes of the tree in ArrayList.

4. Conclusion

In this article, we saw how to flatten a Binary tree using Preorder traversal.

GitHub Link:

https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/FlattenBinaryTreetoLinkedList114.java