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:

1
2
3
4
5
6
7


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

You should convert it to:

1
2
3
4
5


     0
  /     \
5         4
        /   \
       6     7

Examples

Example 1

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


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input:
    1
   /
  2
   \
    3

Output:
    3

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

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

1
2
3
4
5
6
7


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:

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

Approach

Base case: If node is null, return null
Recursive calls: Process left and right subtrees
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
Update references: The recursive calls naturally update parent-child relationships

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


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()
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112


import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


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()
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119


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!();
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120


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

Alternative Implementation

Python Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


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

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

Visual Example

Original Tree:

1
2
3
4
5
6
7


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

Step-by-step transformation:

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

Result:

1
2
3
4
5


     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.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Solutions#

Method 1 - Recursive Post-Order Traversal#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Iterative Approach with Stack#

Alternative Implementation#

Python Iterative#

Analysis#

Algorithm Properties#

Edge Cases#

Visual Example#

Applications#

Time and Space Analysis#