二进制搜索树对n个元素进行排序的复杂性是多少

Question

我们得到了具有n个整数节点的BST。按排序顺序打印所有整数的复杂性是多少？有人能帮忙吗？

Answer 1

要按排序顺序打印，您必须按顺序遍历图形，这是深度优先遍历。

其时间复杂度将是O(n+m(，其中n是节点的数量，m是边的数量。

由于这是一个BST，最大边数为n-1，因此时间复杂度为O(n+n-1(=O(n(。