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.

0 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. skartik on December 16, 2016 at 7:50 pm said:

    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);
    }
    }

  5. Maung Aung on October 14, 2017 at 10:47 am said:

    Can someone show me code hato ask user input a value and check if it’s leaf node and only to delete if it is a tree node.

Leave a Reply to skartik Cancel 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