Solution Developed In:
The Question
For this article, we will be covering Leetcode's '814. Binary Tree Pruning' question. This question is rated as a Medium question.
Question:
Given the
root
of a binary tree, return the same tree where every subtree (of the given tree) not containing a1
has been removed.A subtree of a
node
is a node plus every node that is a descendant ofnode
.
Example:
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Explaining The Question
This Question is rated Medium. Although the question is poorly worded, it is clear that we are given a binary tree and we need to remove all the subtrees that do not contain a 1.
Basically, what we're being ask is 'Do this subtree contain any 1s?'. If so, keep it. If not, remove it.
The tricker part of this question is figuring out what sort of traversal is needed to achive this. But as we need to know if a entire subtree contains a 1, we can use a Post Order Traversal to achieve this. As we will start at the every bottom of every subtree and work our way up, we will know if a subtree contains a 1.
Recommended Knowledge
What do we know?
- We have a binary tree
- This Binary Tree contains nothing but 1s or 0s
- We need to check if all the subtrees contain a 1 or a 0. Meaning we should start at the bottom of the tree and work our way up as to prevent a brute force solution.
How we're going to do it:
We're going to use a Post Order Traversal to traverse the tree starting at the very bottom. We do this because we want each subtree to be checked before we check the parent node. Meaning, that when we check the parent node it already knows if any of it's children contain a 1
.
- Post Order Traversal and start all the way at the bottom of our tree
- Ask if the current node is a empty node or not. If it is, then it cannot have 1 for children. So we report this subtree as in needing of pruning.
- We then ask if the left tree or the right tree contained any
1s
. If it didn't we prune this tree by nullifying it - We then ask if any of the children contained a 1 or not. We do this so we can bubble our results up to the parent nodes that somewhere in the subtree a one does exist. We do this to prevent pruning of entire subtrees.
- We repeat this process until all the nodes have been checked.
- Return the newly pruned tree.
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 in the worst case scenario where the tree is all '1s'.
- Space Complexity: O(h) | Where h is the height of the Binary Tree | Because we're going to store the height of the tree within the Call Stack due to the post order traversal
' 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: 90 ms, faster than 26.96% of JavaScript online submissions for Binary Tree Pruning
- Memory Usage: 42.1 MB, less than 92.19% of JavaScript online submissions for Binary Tree Pruning
The Solution
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var pruneTree = function (root) {
/* -------------------------------------------------------------------------- */
/* 814. Binary Tree Pruning */
/* -------------------------------------------------------------------------- */
/**
* @author Samuel Hinchliffe
* @see {@link linkedin.com/in/samuel-hinchliffe-ðŸš€-2bb5801a5/ | Author's Linkedin }
* @see {@link github.com/Samuel-Hinchliffe}
*/
// So how are we going to do it?
// > We're going to perform post-order traversal
// > where we ask every node:
// > - Does your left tree have a 1 anywhere?
// > - Does your right tree have a 1 anywhere?
// > - If it has no 1, we prune it.
// > - If any of them have a one, we let the parent node know
const post_order_prune = (node) => {
// End of tree. So of course, this tree has no 1s
if (!node) {
return false;
}
// Do either the right or left nodes have 1s?
let left_contains_a_one = post_order_prune(node.left);
let right_contains_a_one = post_order_prune(node.right);
// Left tree hasn't got a 1
if (!left_contains_a_one) {
// Prune it
node.left = null;
}
// Right tree does not have a 1
if (!right_contains_a_one) {
// Prune it
node.right = null;
}
// So did any of our trees contain a 1?
// Let the parent know about this.
// We do this because, you could have a 1 all the way the bottom of the tree.
// Which we need to bubble all the way back up to the parent.
if (left_contains_a_one || right_contains_a_one) {
return true;
}
// After pruning
// Return this nodes value (Truthy or falsely)
return node.val;
};
// Start the prune of children
post_order_prune(root);
// So we have pruned the children, does the root node
// need to be removed?
if (!root.right && !root.left && root.val === 0) {
root = null;
}
// Return the root
return root;
};
Top comments (0)