Remove Half Nodes

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Remove all half nodes (nodes with only one child) from binary tree.

Algorithm

1Post-order: process children first. If node has only left child: return left child. If only right: return right child. Else return node.

Common Pitfalls

•Half node has exactly one child. Post-order replacement. O(n). Leaf nodes and full nodes are kept.

Remove Half Nodes.java

Java

// Approach: DFS postorder. If a node has exactly one child, return that child (remove the half node).
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    // Return the root of the modified tree after removing all the half nodes.
    public Node RemoveHalfNodes(Node root) {
        if (root == null)
            return null;

        root.left = RemoveHalfNodes(root.left);
        root.right = RemoveHalfNodes(root.right);

        if (root.left != null && root.right == null)
            return root.left;
        if (root.right != null && root.left == null)
            return root.right;

        return root;
    }
}

Was this solution helpful?