binary-search-tree - 这个序列在 BST 中插入多少个

Question

4节点二叉搜索树：2143。有3种方法插入并得到相同的结果。

这3种可能的方法是什么？

     1<-2->4 and then 3 would branch left of 4. 

我没有看到任何其他可能的插入排列。

Answer 1

不同的插入顺序会导致不同的布局：

1  ->   2 ->   2   ->   2
       /      / \      / \
      1      1   3    1   3
                           \
                            4

与：

1  ->   2 ->   2   ->   2
       /      / \      / \
      1      1   4    1   4
                         /
                        3

如果您想知道如何获得与通过插入序列 2->1->4->3 获得的布局相同的布局

  2
 / \
1   4
   /
  3

你得到：1->2->4->3、2->1->4->3、2->4->3->1