Deleting all Leaves from a Binary Tree

Problem: Given a binary tree, how do you remove leaves of it?

Solution: By using post-order traversal we can solve this problem (other traversals would also work).

struct BinaryTreeNode* removeLeaves(struct BinaryTreeNode* root) {
	if (root != NULL) 
	{
		if (root->left == NULL && root->right == NULL) 
		{
			free(root);
			return NULL;
		} 
		else
		{
			root->left = removeLeaves(root->left);
			root->right = removeLeaves(root->right);
		}
	}
	return root;
}

Time Complexity: O(n). Where is numbe of nodes in tree.

Write or Comment if you find anything incorrect or better approach.

4 Thoughts on “Deleting all Leaves from a Binary Tree

  1. Please explain the process of calculation of its time complexicity

  2. Anonymous on November 8, 2014 at 7:38 am said:

    This is no good solution, because if you have a tree lets say with hight 3, than you will delete all nodes except of the root.

  3. this code is not working code is wrong pl check it

  4. void removeLeaves(node *root) {
    if (!root)
    return;
    else if (!root->left && !root->right) {
    if (root->par) {
    if (root->par->left == root)
    root->par->left = NULL;
    else
    root->par->right = NULL;
    root->par = NULL;
    }
    delete root;
    } else {
    removeLeaves(root->left);
    removeLeaves(root->right);
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation