Recursive Depth First Search Algorithm to Convert to Full Binary Tree By Removing Single-Child Nodes

Given a binary tree root, remove all nodes with only one child.

Constraints
n ≤ 100,000 where n is the number of nodes in root

Example 1
Input

root = [4, [3, [1, [0, null, null], [2, null, null]], null], null]

Output

[1, [0, null, null], [2, null, null]]

Recursive Depth First Search Algorithm to Convert to a Full Binary Tree

We can recursively remove the nodes of single child (from bottom up). If a node is Null, or it is a leaf node, or it has both children nodes, we keep it. Otherwise, we remove the current node.

Python Recursive Depth First Search Algorithm to Remove Single Child Nodes in a Binary Tree.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeSingleChild(self, root):
        if not root:
            return root
        if not root.left and not root.right:
            return root
        if not root.left:
            return self.removeSingleChild(root.right)
        if not root.right:
            return self.removeSingleChild(root.left)
        root.left = self.removeSingleChild(root.left)
        root.right = self.removeSingleChild(root.right)
        return root

C++ Implementation of DFS Algorithm to Convert to a Full Binary Tree by removing nodes with single child in a binary tree.

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
Tree* removeSingleChild(Tree* root) {
    if (!root) return nullptr;
    if (root->left == root->right) { // both kids are NULL
        return root;
    }
    if (root->left == nullptr || root->right == nullptr) {
        if (root->left) {
            return removeSingleChild(root->left);
        } else {
            return removeSingleChild(root->right);
        }
    }
    root->left = removeSingleChild(root->left);
    root->right = removeSingleChild(root->right);
    return root;
}

Both algorithms/implementation have time complexity O(N) where N is the number of the nodes in the binary tree. The space complexity is also O(N) as we are implicitily using a stack due to Recursion.

–EOF (The Ultimate Computing & Technology Blog) —