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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to check if given node is a leaf node or not bool isLeaf(Node* node) { return (node->left == nullptr && node->right == nullptr); } // Function to convert a binary tree to full tree by removing half nodes // i.e. remove nodes having one children Node* truncate(Node* root) { // base case: empty tree if (root == nullptr) return nullptr; // recursively truncate the left subtree and subtree first root->left = truncate(root->left); root->right = truncate(root->right); // if current node has two children or it is leaf node, // nothing needs to be done if ((root->left && root->right) || isLeaf(root)) return root; // if current node has exactly one child, then delete it and replace // the node by the child node Node* child = (root->left)? root->left: root->right; delete root; return child; } |

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

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

Thanks Praveen. We have fixed the link.