Prune Unary nodes to form Full Binary Tree

Problem

Recall that a full binary tree is one in which each node is either a leaf node, or has two children. Given a binary tree, convert it to a full one by removing nodes with only one child.

For example, given the following tree:

         0
      /     \
    1         2
  /            \
3                 4
  \             /   \
    5          6     7

You should convert it to:

     0
  /     \
5         4
        /   \
       6     7

Examples

Example 1

Input: Tree as shown above
         0
      /     \
    1         2
  /            \
3                 4
  \             /   \
    5          6     7

Output: 
     0
  /     \
5         4
        /   \
       6     7

Explanation: Nodes 1, 2, and 3 have only one child each, so they are removed.

Example 2

Input:
    1
   /
  2
   \
    3

Output:
    3

Explanation: Nodes 1 and 2 have only one child each, so they are removed.

Example 3

Input:
    1
   / \
  2   3
 /   / \
4   5   6

Output:
    1
   / \
  4   3
     / \
    5   6

Explanation: Node 2 has only one child, so it's removed and replaced by 4.

Example 4

Input:
    1

Output:
    1

Explanation: Single node is already a full binary tree (leaf node).

Solutions

Method 1 - Recursive Post-Order Traversal

Intuition

The key insight is to use post-order traversal (process children before parent) to ensure we handle the deepest nodes first. When we encounter a node with only one child, we replace it with its single child and continue the process.

The algorithm works as follows:

1. Recursively process left and right subtrees first
2. If current node has only one child, replace it with that child
3. If current node has two children or is a leaf, keep it as is

Approach

1. Base case: If node is null, return null
2. Recursive calls: Process left and right subtrees
3. Check node type:
   • If node has no children (leaf): return the node
   • If node has only left child: return the processed left child
   • If node has only right child: return the processed right child
   • If node has both children: return the node with updated children
4. Update references: The recursive calls naturally update parent-child relationships

Code

C++

#include <iostream>
#include <queue>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* convertToFullBinaryTree(TreeNode* root) {
        if (!root) return nullptr;
        
        // Process left and right subtrees first (post-order)
        root->left = convertToFullBinaryTree(root->left);
        root->right = convertToFullBinaryTree(root->right);
        
        // If current node has only one child, replace it with that child
        if (!root->left && root->right) {
            // Only right child exists
            return root->right;
        } else if (root->left && !root->right) {
            // Only left child exists
            return root->left;
        }
        
        // Node has either two children or no children (leaf)
        return root;
    }
    
    // Helper function to print tree level by level
    void printLevelOrder(TreeNode* root) {
        if (!root) {
            std::cout << "Empty tree" << std::endl;
            return;
        }
        
        std::queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                if (node) {
                    std::cout << node->val << " ";
                    q.push(node->left);
                    q.push(node->right);
                } else {
                    std::cout << "null ";
                }
            }
            std::cout << std::endl;
        }
    }
    
    // Helper function to create the example tree
    TreeNode* createExampleTree() {
        TreeNode* root = new TreeNode(0);
        root->left = new TreeNode(1);
        root->right = new TreeNode(2);
        root->left->left = new TreeNode(3);
        root->right->right = new TreeNode(4);
        root->left->left->right = new TreeNode(5);
        root->right->right->left = new TreeNode(6);
        root->right->right->right = new TreeNode(7);
        return root;
    }
};

Go

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func convertToFullBinaryTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    // Process left and right subtrees first (post-order)
    root.Left = convertToFullBinaryTree(root.Left)
    root.Right = convertToFullBinaryTree(root.Right)
    
    // If current node has only one child, replace it with that child
    if root.Left == nil && root.Right != nil {
        // Only right child exists
        return root.Right
    } else if root.Left != nil && root.Right == nil {
        // Only left child exists
        return root.Left
    }
    
    // Node has either two children or no children (leaf)
    return root
}

func printInOrder(root *TreeNode) {
    if root == nil {
        return
    }
    
    printInOrder(root.Left)
    fmt.Printf("%d ", root.Val)
    printInOrder(root.Right)
}

func createExampleTree() *TreeNode {
    root := &TreeNode{Val: 0}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 2}
    root.Left.Left = &TreeNode{Val: 3}
    root.Right.Right = &TreeNode{Val: 4}
    root.Left.Left.Right = &TreeNode{Val: 5}
    root.Right.Right.Left = &TreeNode{Val: 6}
    root.Right.Right.Right = &TreeNode{Val: 7}
    return root
}

func main() {
    root := createExampleTree()
    fmt.Print("Original tree (in-order): ")
    printInOrder(root)
    fmt.Println()
    
    fullTree := convertToFullBinaryTree(root)
    fmt.Print("Full binary tree (in-order): ")
    printInOrder(fullTree)
    fmt.Println()
}

Java

import java.util.*;

av
class Solution {
    public TreeNode convertToFullBinaryTree(TreeNode root) {
        if (root == null) return null;
        
        // Process left and right subtrees first (post-order)
        root.left = convertToFullBinaryTree(root.left);
        root.right = convertToFullBinaryTree(root.right);
        
        // If current node has only one child, replace it with that child
        if (root.left == null && root.right != null) {
            // Only right child exists
            return root.right;
        } else if (root.left != null && root.right == null) {
            // Only left child exists
            return root.left;
        }
        
        // Node has either two children or no children (leaf)
        return root;
    }
    
    public void printLevelOrder(TreeNode root) {
        if (root == null) {
            System.out.println("Empty tree");
            return;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    System.out.print(node.val + " ");
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    System.out.print("null ");
                }
            }
            System.out.println();
        }
    }
    
    public void printInOrder(TreeNode root) {
        if (root == null) return;
        
        printInOrder(root.left);
        System.out.print(root.val + " ");
        printInOrder(root.right);
    }
    
    public TreeNode createExampleTree() {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.right.right = new TreeNode(4);
        root.left.left.right = new TreeNode(5);
        root.right.right.left = new TreeNode(6);
        root.right.right.right = new TreeNode(7);
        return root;
    }
    
    // Test cases
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test case 1: Original example
        TreeNode root1 = sol.createExampleTree();
        System.out.print("Original tree (in-order): ");
        sol.printInOrder(root1);
        System.out.println();
        
        TreeNode fullTree1 = sol.convertToFullBinaryTree(root1);
        System.out.print("Full binary tree (in-order): ");
        sol.printInOrder(fullTree1);
        System.out.println();
        
        // Test case 2: Chain of single children
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.left.right = new TreeNode(3);
        
        System.out.print("\nChain tree (in-order): ");
        sol.printInOrder(root2);
        System.out.println();
        
        TreeNode fullTree2 = sol.convertToFullBinaryTree(root2);
        System.out.print("Result (in-order): ");
        sol.printInOrder(fullTree2);
        System.out.println();
    }
}

Kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun convertToFullBinaryTree(root: TreeNode?): TreeNode? {
        if (root == null) return null
        
        // Process left and right subtrees first (post-order)
        root.left = convertToFullBinaryTree(root.left)
        root.right = convertToFullBinaryTree(root.right)
        
        // If current node has only one child, replace it with that child
        return when {
            root.left == null && root.right != null -> {
                // Only right child exists
                root.right
            }
            root.left != null && root.right == null -> {
                // Only left child exists
                root.left
            }
            else -> {
                // Node has either two children or no children (leaf)
                root
            }
        }
    }
    
    fun printInOrder(root: TreeNode?) {
        if (root == null) return
        
        printInOrder(root.left)
        print("${root.`val`} ")
        printInOrder(root.right)
    }
    
    fun createExampleTree(): TreeNode {
        val root = TreeNode(0)
        root.left = TreeNode(1)
        root.right = TreeNode(2)
        root.left!!.left = TreeNode(3)
        root.right!!.right = TreeNode(4)
        root.left!!.left!!.right = TreeNode(5)
        root.right!!.right!!.left = TreeNode(6)
        root.right!!.right!!.right = TreeNode(7)
        return root
    }
}

fun main() {
    val sol = Solution()
    
    val root = sol.createExampleTree()
    print("Original tree (in-order): ")
    sol.printInOrder(root)
    println()
    
    val fullTree = sol.convertToFullBinaryTree(root)
    print("Full binary tree (in-order): ")
    sol.printInOrder(fullTree)
    println()
}

Python

from typing import Optional
from collections import deque

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

class Solution:
    def convert_to_full_binary_tree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """
        Convert binary tree to full binary tree by removing nodes with only one child.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            Root of the converted full binary tree
        """
        if not root:
            return None
        
        # Process left and right subtrees first (post-order)
        root.left = self.convert_to_full_binary_tree(root.left)
        root.right = self.convert_to_full_binary_tree(root.right)
        
        # If current node has only one child, replace it with that child
        if not root.left and root.right:
            # Only right child exists
            return root.right
        elif root.left and not root.right:
            # Only left child exists
            return root.left
        
        # Node has either two children or no children (leaf)
        return root
    
    def print_level_order(self, root: Optional[TreeNode]) -> None:
        """Print tree in level order for visualization."""
        if not root:
            print("Empty tree")
            return
        
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                if node:
                    print(node.val, end=" ")
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    print("null", end=" ")
            print()
    
    def print_in_order(self, root: Optional[TreeNode]) -> None:
        """Print tree in-order traversal."""
        if not root:
            return
        
        self.print_in_order(root.left)
        print(root.val, end=" ")
        self.print_in_order(root.right)
    
    def create_example_tree(self) -> TreeNode:
        """Create the example tree from the problem."""
        root = TreeNode(0)
        root.left = TreeNode(1)
        root.right = TreeNode(2)
        root.left.left = TreeNode(3)
        root.right.right = TreeNode(4)
        root.left.left.right = TreeNode(5)
        root.right.right.left = TreeNode(6)
        root.right.right.right = TreeNode(7)
        return root
    
    def tree_to_list(self, root: Optional[TreeNode]) -> list:
        """Convert tree to list representation for easy comparison."""
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            if node:
                result.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append(None)
        
        # Remove trailing None values
        while result and result[-1] is None:
            result.pop()
        
        return result

def test_convert_to_full_binary_tree():
    """Test the solution with various test cases."""
    sol = Solution()
    
    # Test case 1: Original example
    print("Test Case 1: Original Example")
    root1 = sol.create_example_tree()
    print("Original tree (in-order): ", end="")
    sol.print_in_order(root1)
    print()
    
    full_tree1 = sol.convert_to_full_binary_tree(root1)
    print("Full binary tree (in-order): ", end="")
    sol.print_in_order(full_tree1)
    print("\n")
    
    # Test case 2: Chain of single children
    print("Test Case 2: Chain Tree")
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.left.right = TreeNode(3)
    
    print("Original chain (in-order): ", end="")
    sol.print_in_order(root2)
    print()
    
    full_tree2 = sol.convert_to_full_binary_tree(root2)
    print("Result (in-order): ", end="")
    sol.print_in_order(full_tree2)
    print("\n")
    
    # Test case 3: Already full binary tree
    print("Test Case 3: Already Full Tree")
    root3 = TreeNode(1)
    root3.left = TreeNode(2)
    root3.right = TreeNode(3)
    root3.left.left = TreeNode(4)
    root3.left.right = TreeNode(5)
    
    print("Original tree (in-order): ", end="")
    sol.print_in_order(root3)
    print()
    
    full_tree3 = sol.convert_to_full_binary_tree(root3)
    print("Result (in-order): ", end="")
    sol.print_in_order(full_tree3)
    print("\n")
    
    # Test case 4: Single node
    print("Test Case 4: Single Node")
    root4 = TreeNode(42)
    
    print("Original tree (in-order): ", end="")
    sol.print_in_order(root4)
    print()
    
    full_tree4 = sol.convert_to_full_binary_tree(root4)
    print("Result (in-order): ", end="")
    sol.print_in_order(full_tree4)
    print("\n")
    
    # Test case 5: Empty tree
    print("Test Case 5: Empty Tree")
    root5 = None
    full_tree5 = sol.convert_to_full_binary_tree(root5)
    print(f"Result: {full_tree5}")

if __name__ == "__main__":
    test_convert_to_full_binary_tree()

Rust

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

type OptNode = Option<Rc<RefCell<TreeNode>>>;

fn convert_to_full_binary_tree(root: OptNode) -> OptNode {
    match root {
        None => None,
        Some(node) => {
            let mut node_ref = node.borrow_mut();
            
            // Process left and right subtrees first (post-order)
            let left = convert_to_full_binary_tree(node_ref.left.take());
            let right = convert_to_full_binary_tree(node_ref.right.take());
            
            node_ref.left = left.clone();
            node_ref.right = right.clone();
            
            // If current node has only one child, replace it with that child
            match (&left, &right) {
                (None, Some(_)) => {
                    // Only right child exists
                    right
                }
                (Some(_), None) => {
                    // Only left child exists
                    left
                }
                _ => {
                    // Node has either two children or no children (leaf)
                    drop(node_ref);
                    Some(node)
                }
            }
        }
    }
}

fn print_in_order(root: &OptNode) {
    if let Some(node) = root {
        let node_ref = node.borrow();
        print_in_order(&node_ref.left);
        print!("{} ", node_ref.val);
        print_in_order(&node_ref.right);
    }
}

fn create_example_tree() -> OptNode {
    let root = Rc::new(RefCell::new(TreeNode::new(0)));
    let node1 = Rc::new(RefCell::new(TreeNode::new(1)));
    let node2 = Rc::new(RefCell::new(TreeNode::new(2)));
    let node3 = Rc::new(RefCell::new(TreeNode::new(3)));
    let node4 = Rc::new(RefCell::new(TreeNode::new(4)));
    let node5 = Rc::new(RefCell::new(TreeNode::new(5)));
    let node6 = Rc::new(RefCell::new(TreeNode::new(6)));
    let node7 = Rc::new(RefCell::new(TreeNode::new(7)));
    
    root.borrow_mut().left = Some(node1.clone());
    root.borrow_mut().right = Some(node2.clone());
    node1.borrow_mut().left = Some(node3.clone());
    node2.borrow_mut().right = Some(node4.clone());
    node3.borrow_mut().right = Some(node5);
    node4.borrow_mut().left = Some(node6);
    node4.borrow_mut().right = Some(node7);
    
    Some(root)
}

fn main() {
    println!("Test Case 1: Original Example");
    let root = create_example_tree();
    print!("Original tree (in-order): ");
    print_in_order(&root);
    println!();
    
    let full_tree = convert_to_full_binary_tree(root);
    print!("Full binary tree (in-order): ");
    print_in_order(&full_tree);
    println!();
    
    // Test case 2: Chain of single children
    println!("\nTest Case 2: Chain Tree");
    let root2 = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    if let Some(ref node) = root2 {
        let node2 = Rc::new(RefCell::new(TreeNode::new(2)));
        let node3 = Rc::new(RefCell::new(TreeNode::new(3)));
        
        node.borrow_mut().left = Some(node2.clone());
        node2.borrow_mut().right = Some(node3);
    }
    
    print!("Original chain (in-order): ");
    print_in_order(&root2);
    println!();
    
    let full_tree2 = convert_to_full_binary_tree(root2);
    print!("Result (in-order): ");
    print_in_order(&full_tree2);
    println!();
}

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}

function convertToFullBinaryTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    
    // Process left and right subtrees first (post-order)
    root.left = convertToFullBinaryTree(root.left);
    root.right = convertToFullBinaryTree(root.right);
    
    // If current node has only one child, replace it with that child
    if (!root.left && root.right) {
        // Only right child exists
        return root.right;
    } else if (root.left && !root.right) {
        // Only left child exists
        return root.left;
    }
    
    // Node has either two children or no children (leaf)
    return root;
}

function printInOrder(root: TreeNode | null): void {
    if (!root) return;
    
    printInOrder(root.left);
    process.stdout.write(`${root.val} `);
    printInOrder(root.right);
}

function printLevelOrder(root: TreeNode | null): void {
    if (!root) {
        console.log("Empty tree");
        return;
    }
    
    const queue: (TreeNode | null)[] = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (node) {
                process.stdout.write(`${node.val} `);
                queue.push(node.left);
                queue.push(node.right);
            } else {
                process.stdout.write("null ");
            }
        }
        console.log();
    }
}

function createExampleTree(): TreeNode {
    const root = new TreeNode(0);
    root.left = new TreeNode(1);
    root.right = new TreeNode(2);
    root.left.left = new TreeNode(3);
    root.right.right = new TreeNode(4);
    root.left.left.right = new TreeNode(5);
    root.right.right.left = new TreeNode(6);
    root.right.right.right = new TreeNode(7);
    return root;
}

// Test cases
function testConvertToFullBinaryTree(): void {
    console.log("Test Case 1: Original Example");
    const root1 = createExampleTree();
    process.stdout.write("Original tree (in-order): ");
    printInOrder(root1);
    console.log();
    
    const fullTree1 = convertToFullBinaryTree(root1);
    process.stdout.write("Full binary tree (in-order): ");
    printInOrder(fullTree1);
    console.log("\n");
    
    // Test case 2: Chain of single children
    console.log("Test Case 2: Chain Tree");
    const root2 = new TreeNode(1);
    root2.left = new TreeNode(2);
    root2.left.right = new TreeNode(3);
    
    process.stdout.write("Original chain (in-order): ");
    printInOrder(root2);
    console.log();
    
    const fullTree2 = convertToFullBinaryTree(root2);
    process.stdout.write("Result (in-order): ");
    printInOrder(fullTree2);
    console.log("\n");
    
    // Test case 3: Single node
    console.log("Test Case 3: Single Node");
    const root3 = new TreeNode(42);
    
    process.stdout.write("Original tree (in-order): ");
    printInOrder(root3);
    console.log();
    
    const fullTree3 = convertToFullBinaryTree(root3);
    process.stdout.write("Result (in-order): ");
    printInOrder(fullTree3);
    console.log();
}

// Run tests
testConvertToFullBinaryTree();

Complexity

• ⏰ Time complexity: O(n) where n is the number of nodes - we visit each node exactly once
• 🧺 Space complexity: O(h) where h is the height of the tree - for the recursion stack

Method 2 - Iterative Approach with Stack

Code

Python

from typing import Optional
from collections import deque

class SolutionIterative:
    def convert_to_full_binary_tree_iterative(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """
        Iterative approach using post-order traversal with explicit stack.
        """
        if not root:
            return None
        
        # Handle single node case
        if not root.left and not root.right:
            return root
        
        # Use stack for post-order traversal
        stack = []
        last_visited = None
        current = root
        parent_map = {}  # Map child to parent
        
        # Build parent map and identify nodes to remove
        nodes_to_process = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            
            # Check if node has only one child
            has_left = node.left is not None
            has_right = node.right is not None
            
            if (has_left and not has_right) or (not has_left and has_right):
                nodes_to_process.append(node)
            
            if node.left:
                parent_map[node.left] = node
                queue.append(node.left)
            if node.right:
                parent_map[node.right] = node
                queue.append(node.right)
        
        # Process nodes with single children from bottom up
        for node in reversed(nodes_to_process):
            parent = parent_map.get(node)
            replacement = node.left if node.left else node.right
            
            if parent:
                if parent.left == node:
                    parent.left = replacement
                else:
                    parent.right = replacement
                
                if replacement:
                    parent_map[replacement] = parent
            else:
                # This is the root node
                root = replacement
        
        return root

def test_iterative_approach():
    """Test the iterative solution."""
    sol = SolutionIterative()
    
    # Create test tree
    root = TreeNode(0)
    root.left = TreeNode(1)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.right.right = TreeNode(4)
    root.left.left.right = TreeNode(5)
    root.right.right.left = TreeNode(6)
    root.right.right.right = TreeNode(7)
    
    print("Iterative Approach Test")
    print("Original tree (in-order): ", end="")
    sol_main = Solution()  # Use main solution for printing
    sol_main.print_in_order(root)
    print()
    
    full_tree = sol.convert_to_full_binary_tree_iterative(root)
    print("Result (in-order): ", end="")
    sol_main.print_in_order(full_tree)
    print()

if __name__ == "__main__":
    test_iterative_approach()

Analysis

Algorithm Properties

Post-Order Traversal Benefits:

• Ensures children are processed before parents
• Naturally handles the "bottom-up" removal of nodes
• Maintains tree structure integrity during transformation
• Simple and elegant recursive solution

Tree Transformation Rules:

• Nodes with two children remain unchanged
• Leaf nodes (no children) remain unchanged
• Nodes with only one child are removed and replaced by their child
• The replacement maintains the original tree's connectivity

Edge Cases

1. Empty tree: Return null
2. Single node: Already a full binary tree (leaf)
3. Root with single child: Root is replaced by its child
4. All nodes have single children: Results in a single leaf node
5. Already full binary tree: No changes needed

Visual Example

Original Tree:

         0
      /     \
    1         2
  /            \
3                 4
  \             /   \
    5          6     7

Step-by-step transformation:

1. Process leaf nodes: 5, 6, 7 (no change - they're leaves)
2. Process node 3: has only right child (5) → replace 3 with 5
3. Process node 1: now has only left child (5) → replace 1 with 5
4. Process node 2: has only right child (4) → replace 2 with 4
5. Process node 0: now has left child (5) and right child (4) → keep as is

Result:

     0
  /     \
5         4
        /   \
       6     7

Applications

• Tree optimization: Removing unnecessary intermediate nodes
• Expression trees: Simplifying parse trees in compilers
• Decision trees: Pruning nodes that don't contribute to decisions
• File system hierarchies: Removing empty intermediate directories
• Binary search trees: Maintaining structure after deletions

Time and Space Analysis

Recursive Approach:

• ⏰ Time: O(n) - visit each node once
• 🧺 Space: O(h) - recursion stack depth equals tree height

Properties:

• Best case: O(log n) space for balanced tree
• Worst case: O(n) space for skewed tree
• Memory efficient: Only uses recursion stack, no additional data structures

The recursive post-order approach is optimal for this problem, providing both simplicity and efficiency while naturally handling the tree transformation requirements.