Can anyone clarify the definition of BST with duplicated node values? (picture illustration)


  • 1

    I have seen many top solutions using the following algorithm for serialization:

    • Pre-order traversal to store all node values sequentially in a string with a special separator char between adjacent values.

    The absence of "NULL" node notation is the benefit we get from BST compared to Problem 297 (generic binary tree).

    However, when it comes to deserialization, I am not sure how you can restore to the structure of the original BST if there are duplicated node values. The key question is that

    • if a child node has the same value as its parent, should it be inserted to left or right sub-tree?

    Forgiven me as I am not from Computer Science major. According to the well known book,

    • "Introduction to Algorithms, 3rd Ed" (by T. Cormen, C. Leiserson, R. Rivest and C. Stein), page 287,

    the key of a node in BST >= any node key in left sub-tree and <= any node key value in right sub-tree. So if I have a BST with all identical node key values, there will be many ways to re-construct the BST.

    However, from Wikipedia, the definition of BST makes it strict on left sub-tree, i.e., a node's value is strictly greater than (>) any node's value in its left sub-tree, which will ensure the uniqueness of insertion place if a new node coming in with a duplicated key value with an existing node in BST.

    Therefore, the consequence is that if given a BST with all identical node values, the serialized string is trivial and there is no way to restore the original structure if using the definition from "Introduction to Algorithms, 3rd Ed".

    Since we certainly cannot use Wikipedia as an official source for scientific terminology, so I appreciate if someone can clarify the "commonly accepted" definition of BST when there are duplicated node values. Thanks.

    Are they all considered BST? Or this problem guarantees that there is no duplicated node values in given BST? @administrators
    0_1485543002090_BST.JPG


  • 0

    As far as I know, Leetcode always uses this definition. Meaning there are no duplicates.


Log in to reply
 

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