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)
Loading...

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
Praveen
Guest

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