Missing test-case - duplicate values ?


  • 0
    P

    Do you have a test-case where the value to be deleted occurs multiple times in BST ?


  • 0

    @prashrockgmail.com I'm not sure if this is possible to test or for the coder to understand which node he should delete, for example suppose that we have the following tree

             1
            /
          1
         /
        1
    

    The input would be something like [1, 1, 1] 1
    How would you figure out which 1 to delete?

    In production usually delete would look for a node address instead of value, so comparing would be based on address which is tricker than this problem, reason is that you have to actually remove the node and insert another one inplace of it. But in this problem you could just get away with swapping values and leave the original node intact.


  • 1
    P

    Thanks k', I was just pointing out that this should be mentioned in the problem statement or tested by OJ..
    For instance, say duplicates are allowed (as in your example [1, 1, 1] 1), I would expect the user to delete all occurences of value from BST.

    Just my 2 c


  • 0

    @prashrockgmail-com Nice question! Thanks for your feedback, maybe we should do something about it @1337c0d3r .


  • 0

    @prashrockgmail.com No, this is not possible because typically in BST you can't have duplicate keys. Of course, you can define a BST with duplicates, but that's not the case here.


  • 0

    how could a BST contain duplicate values?


  • 0

    @jasonshieh @1337c0d3r I kind of doubt it that there should be no duplicates in default. The following paragraph is quoted from wiki

    The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and not greater than all keys in the right sub-tree.

    Which directly implies that the root can be equal to the right sub-tree resulting in duplicates.


  • 1

    @LHearen Someone screwed up there. That sentence references the CLRS book and the definition in the actual book differs. The book says:

    Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤ x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.

    Ok so that allows duplicates even more, namely on both sides.

    Some other sources say "smaller/larger", for example Sedgewick's "Algorithms" book:

    the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

    Anyway... as far as I know, on LeetCode, BSTs have always used "smaller"/"larger", including the Validate Binary Search Tree problem which contains a definition.

    The problem asking us to "delete the node with the given key in the BST" also means the key doesn't appear in more than one node.

    All that said, I think it would be good if the first "BST" in the problem were a link to that "Validate ..." problem. That would make it really clear.


  • 1

    @StefanPochmann Stefan, thanks for what you did. It actually should be clarified in each problem statement to avoid ambiguity. As far as I know, there are quite a lot standards out there. So to make the Leetcode more stable and more credible, I think your word mentioned should really be paid more attention to.

    Clarity should be an important factor that affects the impressions of the Leetcode presents to the world. @1337c0d3r


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.