R – Delete multiple nodes from a binary search tree

binary-search-treec

I have a binary search tree created in C. The problem is I can't find a efficient way to delete all the nodes with e.g., id>5.

When I traverse the tree, if I delete a node, the recursion is getting error, because the structure is not the same.

Is there any way, instead of using a helping stack to keep the data before delete them from the tree?

Best Answer

Did you try postorder?
Delete the node after its children.

Related Solutions

Finding height in Binary Search Tree

The problem lies in your base case.

"The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero." - Wikipedia

If there is no node, you want to return -1 not 0. This is because you are adding 1 at the end.

So if there isn't a node, you return -1 which cancels out the +1.

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

Difference between binary tree and binary search tree

Binary tree: Tree where each node has up to two leaves

  1
 / \
2   3

Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent.

  2
 / \
1   3

Best Answer

Related Solutions

Finding height in Binary Search Tree

Difference between binary tree and binary search tree

Related Topic