We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
Example 1:
Input: [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.



Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]




Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]




Note: 

The binary tree will have at most 200 nodes.
The value of each node will only be 0 or 1.

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code:
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        

Solutions:
class Solution:

	def pruneTreeHelper(self, root: TreeNode) -> TreeNode:
		if not root:
			return None
		left = self.pruneTreeHelper(root.left)
		right = self.pruneTreeHelper(root.right)
		if not left:
			root.left = None
		if not right:
			root.right = None
		if root.val == 0 and root.right is None and (root.left is None):
			return None
		else:
			return root

	def pruneTree(self, root: TreeNode) -> TreeNode:
		return self.pruneTreeHelper(root)


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:
		if not root:
			return None
		root.left = self.pruneTree(root.left)
		root.right = self.pruneTree(root.right)
		if not root.left and (not root.right) and (root.val == 0):
			return None
		return root


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:

		def prune(node: TreeNode) -> bool:
			if not node:
				return True
			left_prune = prune(node.left)
			right_prune = prune(node.right)
			if prune(node.left):
				node.left = None
			if prune(node.right):
				node.right = None
			return node.val == 0 and left_prune and right_prune
		if prune(root):
			return None
		return root


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:

		def check(node):
			if not node.left:
				l = True
			else:
				l = check(node.left)
			if not node.right:
				r = True
			else:
				r = check(node.right)
			if l:
				node.left = None
			if r:
				node.right = None
			return l and r and (node.val == 0)
		ans = TreeNode()
		ans.right = root
		check(ans)
		return ans.right


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:

		def dfs(node):
			if not node:
				return False
			a1 = dfs(node.left)
			a2 = dfs(node.right)
			if not a1:
				node.left = None
			if not a2:
				node.right = None
			return node.val == 1 or a1 or a2
		return root if dfs(root) else None


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:

		def prune_tree_helper(root):
			if root:
				curr_res = True if root.val == 0 else False
				left_res = prune_tree_helper(root.left)
				right_res = prune_tree_helper(root.right)
				if left_res:
					root.left = None
				if right_res:
					root.right = None
				return curr_res and left_res and right_res
			else:
				return True
		res = prune_tree_helper(root)
		if res:
			return None
		else:
			return root


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:
		return root if self.dfs(root) else None

	def dfs(self, root):
		if not root:
			return False
		l = self.dfs(root.left)
		r = self.dfs(root.right)
		if not l:
			root.left = None
		if not r:
			root.right = None
		return root.val == 1 or l or r


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:

		def helper(root):
			if not root:
				return False
			lone = helper(root.left)
			rone = helper(root.right)
			if not lone:
				root.left = None
			if not rone:
				root.right = None
			if root.val == 1 or lone or rone:
				return True
			else:
				return False
		if helper(root):
			return root
		else:
			return None


class Solution:

	def pruneTree(self, root: TreeNode) -> TreeNode:
		if root == None:
			return None
		left_sub = self.pruneTree(root.left)
		right_sub = self.pruneTree(root.right)
		if root.val == 0 and left_sub == None and (right_sub == None):
			return None
		root.left = left_sub
		root.right = right_sub
		return root