Learn how to flatten a binary tree to a linked list.
Given a binary tree we have to arrange all the elements of it to the right node of the parent node such that the new tree looks like a linked list and do this in place.
Example
Input:
1
/ \
2 5
/ \ \
3 4 6
Output:
1
\
2
\
3
\
4
\
5
\
6
We are going to see two different solutions for this.
1. Which works using an extra data structure (stack or queue). Queue for our case.
2. A recursive approach using DFS.
Flatten a binary tree to a linked list using queue.
Conceptually this is how it works.
- Traverse the binary tree using pre-order traversal and store each element in the queue.
- Then iterate the queue and add them to the right of the parent node in binary tree.
const flatten = (root) => {
const head = root;
let queue = [];
//To create new element
class Node {
constructor(key){
this.key = key,
this.left = null,
this.right = null
}
}
//Store each element of tree in a queue using pre-order traversal
(function traverse(root){
if (!root) return;
queue.push(root.key);
traverse(root.left)
traverse(root.right)
}(head));
//Update all the elements to the right
(function change(root){
if (!root) return;
queue.shift();
root.right = root.left = null;
while(queue.length) {
const val = queue.shift();
root.right = new Node(val);
root = root.right;
}
}(root));
};
Input:
const tree = new BST();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
const root = tree.getHead();
flatten(root);
console.log(root);
Output:
11
\
7
\
5
\
3
\
9
\
15
Time complexity: O(n)(tree traversal) + O(n)(queue) = O(n).
Space complexity: O(n).
Flatten a binary tree using DFS.
In this approach we traverse the tree and get each node keep adding to the right of parent node.
const flatten = (root) => {
(function dfs(root, newTail = null) {
if (!root) return newTail;
//Traverse the list with DFS
const right = dfs(root.right, newTail) || newTail;
const left = dfs(root.left, right);
//Flatten the tree
root.right = left;
root.left = null;
return root;
}(root))
}
Input:
const tree = new BST();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
const root = tree.getHead();
flatten(root);
console.log(root);
Output:
11
\
7
\
5
\
3
\
9
\
15
Time complexity: O(n).
Space complexity: O(n) considering the call stack.