Convert given binary tree to full tree by removing half nodes

Given a binary tree, convert it to full tree by removing half nodes (remove nodes having one children).


For example, binary tree shown on the left can be converted to binary tree shown on the right

Convert Binary Tree to Full Tree


The idea is to traverse the tree in bottom-up fashion and convert left and right subtree first before processing a node. Then for each node,

  • if it has two children or it is a leaf node, nothing needs to be done.
  • if it has exactly one child, we delete it and replace the node by the child node.

C++ implementation –

Download   Run Complete Code

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Link to image is broken. Would you please fix it?