Given a binary tree, convert it to full tree by removing half nodes (remove nodes having one children).
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 –
// Data structure to store a Binary Tree node
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)
// 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))
// 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;
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.