814. Binary Tree Pruning 🚀

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 a 1 has been removed.

A subtree of a node is a node plus every node that is a descendant of node.

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

1. Binary Tree
2. Depth First Search
3. Post Order Traversal
4. Recursion

What do we know?

1. We have a binary tree
2. This Binary Tree contains nothing but 1s or 0s
3. 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.

1. Post Order Traversal and start all the way at the bottom of our tree
2. 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.
3. 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
4. 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.
5. We repeat this process until all the nodes have been checked.
6. 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;
};