Remove Half Nodes

JavaView on GFG

Time: O(n)

Space: O(h)

Problem Overview

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

See our study guide for structured GFG and LeetCode practice.

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?