Skip to content

Problem 3.2: Is BST (100 pts)

Problem

Write a function is_bst, which takes a Tree t and returns True if, and only if, t is a valid binary search tree(BST).

A BST is recursively defined as follows:

  • A leaf is a valid BST
  • A Tree t is a valid BST if all the following conditions hold simultaneously:
  • t has at most two branches
  • All branches of t are valid BSTs
  • All labels from the left branch of t are less than or equal to the label of t
  • All labels from the right branch of t are greater than the label of t

An example of a BST is:
2_3_4

Note: If a node has only one branch, that branch could be considered either the left or right branch. You should take this into consideration.

There is more than one way to solve this problem. Can you come up with more solutions?

编写一个函数 is_bst，它接受一个树 t，当且仅当 t 是一个有效的二叉搜索树（BST）时返回 True。

BST 的递归定义如下：

  • 一个叶子节点是一个有效的 BST
  • 一个树 t 是一个有效的 BST，当且仅当以下所有条件同时成立：
  • t 最多有两个分支
  • t 的所有分支都是有效的 BST
  • t 的左分支中的所有标签都小于或等于 t 的标签
  • t 的右分支中的所有标签都大于 t 的标签

一个 BST 的示例是：
2_3_4

注意：如果一个节点只有一个分支，该分支可以被视为左分支或右分支。你应该考虑到这一点。

解决这个问题的方法不止一种。你能想出更多的解决方案吗？

def is_bst(t):
    """Returns True if the Tree t has the structure of a valid BST.

    >>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t1)
    True
    >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
    >>> is_bst(t2)
    False
    >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t3)
    False
    >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
    >>> is_bst(t4)
    True
    >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
    >>> is_bst(t5)
    True
    >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
    >>> is_bst(t6)
    True
    >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
    >>> is_bst(t7)
    False
    """
    "*** YOUR CODE HERE ***"

Hints

Hint: It may be helpful to write helper functions bst_min and bst_max that return the minimum and maximum label, respectively, in the Tree if it is a valid binary search tree.

  • 编写辅助函数 bst_min 和 bst_max 可能会有帮助，它们分别返回树中的最小和最大标签，如果它是有效的二叉搜索树。