Delete a Tree
Level: L3-L4 Topics: Binary Trees, Memory Management, Tree Traversal
Problem Statement
You are given the root of a binary tree. Each node has pointers to its left and right children, but no parent pointer. Your task is to delete every node in the tree individually (i.e., free each node's memory one at a time).
Background & Constraints
- Each node stores a value and pointers to its left and right children only.
- There are no parent pointers available.
- You must delete (free) each node individually — you cannot simply discard the root and let a garbage collector handle the rest.
- The tree can have up to 10^5 nodes.
Examples
Example 1:
A standard post-order traversal would visit nodes in order 4, 5, 2, 3, 1 — deleting children before their parent.
Example 2:
Hints & Common Pitfalls
- The straightforward approach is a post-order traversal (left, right, then delete current node). This uses O(h) stack space where h is the height of the tree.
- Common mistake: Many candidates instinctively want to use parent pointers. The problem explicitly states there are none — you must work with only child pointers.
- Constant memory follow-up: The interviewer will likely ask you to do this in O(1) extra space. Think about how you can restructure the tree as you go. Consider a technique where you rotate nodes to eliminate left children before deleting.
- Morris-style deletion: You can flatten the tree into a right-only chain using rotations, then walk down the chain deleting nodes one by one. This avoids recursion and any auxiliary stack.
- Be careful not to access a node after you have deleted it — save the next pointer before freeing.
Follow-Up Questions
- Can you delete the tree using O(1) auxiliary memory (no recursion stack, no explicit stack)?
- What is the time complexity of your constant-memory solution? Is it still O(n)?
- How would the problem change if you did have parent pointers?
- What if the tree is a general tree (not binary) with an arbitrary number of children per node?