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 sameTreeNode
class where theright
child pointer points to the next
node in the list and theleft
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
What do we know?
- We have a binary tree (Most times, it could be empty)
- We need to flatten the tree into a linked list
- We need to traverse the tree in post order to achieve this for O(h) space
- 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.
- Use
post_order_traversal
to get the nodes in post order - Keep traversing the nodes in post order until we find a node that has a
left
node. - Once we have detected that
left node
we're going to initialise a new pointer calledlefts_right_most_node
. His job is to find theroot.left
further right node. We're going to use awhile
loop to keep getting theright
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 thecurrent
right node. We do this because, we're going to merge the 2 sub trees into one. - Once we have found the
lefts_right_most_node
we're going to connect thelefts_right_most_node
to thecurrent
right node. - We then overwrite the right node of the
current
node with thelefts_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. - We then erase the
left
node of thecurrent
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. - 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;
};
Top comments (0)