CODEWITHSUNDEEP
ctreebinary-treebinary-search-tree
Nikolaos Maliganis
Nikolaos Maliganis

Reputation: 41

BST Binary Tree Remove function in C the leaves with value = 0

I am trying to create a function in C that should be able to remove (delete) all the leaves from a binary tree (BST), which is passed as a parameter, with zero value (0) and the return result will be the number of the deleted leaves. NOTE: Not the nodes with value = 0 but ONLY the leaves. For example to the BST on the figure:

enter image description here

the function will return 2 (after removing the red circled zeros).

Upvotes: 0

Views: 425

Answers (1)

Marcellus
Marcellus

Reputation: 1385

This is a pseudo code to do it:

int delete_zero_leaves (node){
    int deleted
    delete_zero_leaves_aux (node, &deleted);
    return deleted
}

pointer delete_zero_leaves_aux (node, deleted){
    boolean is_leaf = true
    // if there is a child
    if (node->left != NULL){
            // passing deleted by reference
            node->left = delete_zero_leaves_aux (node->left, &deleted)
            is_leaf = false
    }
    // if there is a child on the right side
    if (node->right != NULL){
            // passing deleted by reference
            node->right = delete_zero_leaves_aux (node->right, &deleted)
            is_leaf = false
    }
    if (is_leaf AND node->value == 0){
        free(node)
        deleted += 1
        return NULL
    }
    return node
}

Since you said the node has no pointer the its own father, you can return a pointer and set the value of the father's pointer (left or right).

Upvotes: 3

Related Questions