1. There are 24 (4!) different orders of 1, 2, 3, 4. How many orders can produce the same shape as the 2, 1, 4, 3 ?
 

Transcribed Image Text:

The shape of binary search tree depends on the order of the input. For example, there are 3! = 6 different orders of 1, 2, 3, which create 5 different shapes: • If the input order is 1, 2, 3, the binary search tree is in Fig. 4 (a). • If the input order is 1, 3, 2, the binary search tree is in Fig. 4 (b). • If the input order is 2, 1, 3, the binary search tree is in Fig. 4 (c). • If the input order is 2, 3, 1, the binary search tree is in Fig. 4 (c). • If the input order is 3, 1, 2, the binary search tree is in Fig. 4 (d). • If the input order is 3, 2, 1, the binary search tree is in Fig. 4 (e). 1 2 3 1 2 3 1 2 3 1 2 3 1 2 (a) (b) (c) (d) (e) Figure 4: Binary search trees constructed from different input order of 1, 2, 3. 3 The shape of binary search tree depends on the order of the input. For example, there are 3! = 6 different orders of 1, 2, 3, which create 5 different shapes: • If the input order is 1, 2, 3, the binary search tree is in Fig. 4 (a). • If the input order is 1, 3, 2, the binary search tree is in Fig. 4 (b). • If the input order is 2, 1, 3, the binary search tree is in Fig. 4 (c). • If the input order is 2, 3, 1, the binary search tree is in Fig. 4 (c). • If the input order is 3, 1, 2, the binary search tree is in Fig. 4 (d). • If the input order is 3, 2, 1, the binary search tree is in Fig. 4 (e). 1 2 3 1 2 3 1 2 3 1 2 3 1 2 (a) (b) (c) (d) (e) Figure 4: Binary search trees constructed from different input order of 1, 2, 3. 3

Answer rating: 100% (QA)

Answer Only 2 orders can produce the same as the 2 1 4 3 Explanation Here the ... View the full answer