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 given 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.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Praveen
Guest
Praveen

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

wpDiscuz