Binary Tree Pruning

Solution to Prune Binary Tree

Problem Description

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 node is node plus every node that is a descendant of node.

Naive Approach

A naive approach would involve traversing the tree and, for each node, determining if the subtree rooted at that node contains a 1. If it doesn't, remove the subtree. This can be done recursively.

Algorithm:

1. Define a recursive function containsOne(node) that returns true if the subtree rooted at node contains a 1, and false otherwise.
2. In containsOne(node):
   • If node is null, return false.
   • Recursively check the left and right subtrees.
   • Return true if node.val is 1 or either of the recursive calls returned true.
3. Define a function pruneTree(root):
   • If root is null, return null.
   • Recursively prune the left and right subtrees.
   • If containsOne(root) is false, return null; otherwise, return root.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pruneTree(root):
    if not root:
        return None
    
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)

    if root.val == 0 and not root.left and not root.right:
        return None
    
    return root

Time Complexity: O(N^2) in the worst case, where N is the number of nodes in the tree. This is because for each node, we might have to traverse its entire subtree to check if it contains a 1.

Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack.

Optimal Approach

An optimized approach combines the pruning and the check for the presence of 1 into a single recursive function. This eliminates redundant traversals.

Algorithm:

1. Define a recursive function pruneAndCheck(node) that returns true if the subtree rooted at node (after pruning) contains a 1, and false otherwise. This function also prunes the tree.
2. In pruneAndCheck(node):
   • If node is null, return false.
   • Recursively prune and check the left and right subtrees.
   • Update node.left and node.right based on the results of the recursive calls.
   • Return true if node.val is 1 or either of the recursive calls returned true.
3. In the main function pruneTree(root):
   • Call pruneAndCheck(root).
   • Return root if pruneAndCheck(root) returned true, otherwise return None.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pruneTree(root):
    def prune_and_check(node):
        if not node:
            return False

        left_contains_one = prune_and_check(node.left)
        right_contains_one = prune_and_check(node.right)

        if not left_contains_one:
            node.left = None
        if not right_contains_one:
            node.right = None

        return node.val == 1 or left_contains_one or right_contains_one

    if prune_and_check(root):
        return root
    else:
        return None

Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack.

Edge Cases

• Empty Tree: If the input tree is empty (root is null), the function should return null.
• Tree with Only Zeros: If the tree contains only nodes with the value 0, the function should return null.
• Tree with Only Ones: If the tree contains only nodes with the value 1, the function should return the original tree.
• Mixed Tree: The tree contains a mix of 0s and 1s, which require pruning of specific subtrees.