Daily Coding Problem #1444

SingleChildTrimmer.java

/**

Good morning! Here's your coding interview problem for today.

This problem was asked by Yahoo.

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
***/

public TNode trimmer(TNode root){
  
  if(root == null || isLeaf(root)){ // root empty or both children null
    return root;
  }
  if(root.left == null || root.right == null){
    // only one child null
    if(root.left == null)
        return trimmer(root.right); // trim the current root 
    if(root.right == null)
        return trimmer(root.left); // trim the current root  
  } else {
    // this root node has two children, keep it and prune its children if needed.
     root.left = trimmer(root.left);
     root.right = trimmer(root.right);
     return root;
  }
}