# Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree

Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree | ninjasquad

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.

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).

GD Star Rating