CODEWITHSUNDEEP
binary-search-tree
warpstar
warpstar

Reputation: 483

How many for this sequence to insert in BST

4 node Binary Search tree: 2143. there are 3 ways to insert and get the same result.

What are those 3 possible ways? 

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

I do not see any other possible insertion permuations.

Upvotes: 0

Views: 167

Answers (1)

Attila
Attila

Reputation: 28762

different orders of insertion can result in different layouts:

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

vs:

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

If you are wondering how you can get to the same layout as the one obtained by the insertion sequence 2->1->4->3

  2
 / \
1   4
   /
  3

You get: 1->2->4->3, 2->1->4->3, 2->4->3->1

Upvotes: 1

Related Questions