Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

prune-a-binary-tree

Example 1:
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.

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

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

Constraints:
The number of nodes in the tree is in the range [1, 200].
Node.val is either 0 or 1.

Recursive Algorithm to Prune a Binary Tree

We can solve this problem by Recursion. We can recursively prune the left sub tree and right sub tree, and if both sub trees are empty after pruning, then we can also remove current node if it is not one. We start calling Recursion Top Down, and then when the recursion goes to the leaves, then the process is backwards from bottom to top.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        
        def dfs(root):
            if not root:
                return
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            if not root.left and not root.right and root.val != 1:
                return None
            return root
        
        return dfs(root)

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        
        def dfs(root):
            if not root:
                return
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            if not root.left and not root.right and root.val != 1:
                return None
            return root
        
        return dfs(root)

The time complexity of this Recursive algorithm (in the fashion of Depth First Search DFS) is O(N) where N is the number of the nodes in the binary tree. The space complexity is O(H) where H is the height of the binary tree, and H could be in the worst case equal to N e.g. if each node of a binary tree contains only one child (or a singly linked list).

Recursive Algorithm to Prune a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading…

690 words
Last Post: Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph)
Next Post: Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree