Problem

Given a binary tree, write an algorithm to delete it completely from memory. The deletion process should ensure that every node in the binary tree is properly deallocated, thereby freeing up all used resources.

This is one of the basic problem in trees. if you are new to trees then this problem will help you build your foundation.

Examples:

Example 1:

1
2
3
4
5
6
7
8
9

Input: root = [1,2,3,4,5]
         1
        / \
       2   3
      / \
     4   5
 
Output: The binary tree is deleted.
Explanation: All nodes (1, 2, 3, 4, 5) are deallocated, ensuring the binary tree no longer exists in memory.

Example 2:

1
2
3
4
5
6
7

Input: root = [10, 20]
         10
        /
       20
 
Output: The binary tree is deleted.
Explanation: All nodes (10, 20) are deallocated.

Example 3:

1
2
3

Input: Empty tree (None or null)
Output: No action required, as the tree is already deleted.
Explanation: There are no nodes to delete.

Solution

Method 1 - Using Postorder Traversal

  • The binary tree can be thought of as a recursive data structure where each node contains references to two child nodes. To delete the entire tree, we need to recursively delete each node starting from the root and moving down to its children.
  • The purpose of recursion here ensures that nodes at the lowest level (leaf nodes) are deallocated first, followed by their parent nodes, ensuring nodes are deleted properly.

Approach

  1. Traverse recursively: Start at the root and recursively traverse each subtree (left and right children).
  2. Delete nodes: Deallocate the nodes in post-order fashion (delete left child, right child, then the parent).
  3. Base condition: If the node is None, return immediately because there is nothing to delete.

To delete a binary tree, all node objects must be set to null, allowing garbage collection to handle the cleanup. In C/C++, however, you need to manually deallocate the memory.

Code

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

class Solution {
    public void deleteTree(TreeNode root) {
        // Base condition - if the root is null, return
        if (root == null) {
            return;
        }

        // Recursively delete the left subtree
        deleteTree(root.left);

        // Recursively delete the right subtree
        deleteTree(root.right);

        // Delete the current node
        System.out.println("Deleting node with value: " + root.value);
        root.left = null;
        root.right = null;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def deleteTree(self, root):
        # Base condition - if the root is None, return
        if root is None:
            return
        
        # Recursively delete the left subtree
        self.deleteTree(root.left)
        
        # Recursively delete the right subtree
        self.deleteTree(root.right)
        
        # Delete the current node (in Python, making it None)
        print(f"Deleting node with value: {root.value}")
        root.left = None
        root.right = None

Complexity

  • ⏰ Time complexity: O(n) - Every node in the tree needs to be visited once to delete it. For a binary tree with n nodes, we perform n deletions.
  • 🧺 Space complexity: O(h) - The recursion stack will hold h function calls at most, where h is the height of the tree. In case of a completely balanced tree, h = log(n).