challenge-61

Full Binary Tree

This problem was asked by Google.

Description

Given a binary tree, remove the nodes in which there is only 1 child, so that the binary tree is a full binary tree.

So leaf nodes with no children should be kept, and nodes with 2 children should be kept as well.

Example

Given this tree:
    1
   / \ 
  2   3
 /   / \
0   9   4

We want a tree like:
    1
   / \ 
  0   3
     / \
    9   4