# 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

rootof a binary tree, return the same tree where every subtree (of the given tree) not containing a

1has been removed.

A subtree of a

nodeis 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

# 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**)*| Whereis the number of nodes in our*n*| As we’re going to traverse all of the nodes within the tree in the worst case scenario where the tree is all ‘1s’.*Binary Tree* - Space Complexity:
*O(**h**)*| Whereis the height of the*h*| Because we’re going to store the height of the tree within the Call Stack due to the post order traversal*Binary Tree*

‘ ** Could this be improved?** ‘ Yes! Morris Traversal could do this problem in

**. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don’t use it here.**

*O(1) space complexity*# Leetcode Results:

See Submission Link:

- Runtime: 90 ms, faster than
of JavaScript online submissions for Binary Tree Pruning*26.96%* - Memory Usage: 42.1 MB, less than
of JavaScript online submissions for Binary Tree Pruning*92.19%*

# 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;

};