2. [12] The function num_orders takes a list 1st giving the insertion order of elements into an initially empty BST. For example, [2, 1, 3] means to insert 2, then insert 1, then insert 3. The function returns the total number of insertion orders (including 1st) that produce the same BST that 1st produces. Here is a sample call of num_orders: >>> num_orders([2, 1, 3]) 2 The return value is 2 because there are 2 insertion orders, [2, 1, 3] and [2, 3, 1], that produce the same BST as produced by [2, 1, 3]. Note that 1st can contain duplicates. Let's agree that equal elements go into the left subtree (not the right subtree) For example, the root of the tree for the insertion sequence [4, 4] has 4 as its left node and an empty right subtree. Implement num_orders Requirements . Your code must be written in Python 3, and the filename must be num_orders.py. We will grade only the num_orders function; please do not change its signature in the starter code. include as many helper functions as you wish Write-up: in your ps2.pdf/ps2.tex files, include an explanation of how your code works. Please include a formal proof of correctness. 2. [12] The function num_orders takes a list 1st giving the insertion order of elements into an initially empty BST. For example, [2, 1, 3] means to insert 2, then insert 1, then insert 3. The function returns the total number of insertion orders (including 1st) that produce the same BST that 1st produces. Here is a sample call of num_orders: >>> num_orders([2, 1, 3]) 2 The return value is 2 because there are 2 insertion orders, [2, 1, 3] and [2, 3, 1], that produce the same BST as produced by [2, 1, 3]. Note that 1st can contain duplicates. Let's agree that equal elements go into the left subtree (not the right subtree) For example, the root of the tree for the insertion sequence [4, 4] has 4 as its left node and an empty right subtree. Implement num_orders Requirements . Your code must be written in Python 3, and the filename must be num_orders.py. We will grade only the num_orders function; please do not change its signature in the starter code. include as many helper functions as you wish Write-up: in your ps2.pdf/ps2.tex files, include an explanation of how your code works. Please include a formal proof of correctness