Problem 2 (8 marks) Let T be a binary search tree with n nodes. Every noder in T has a key (denoted by x key), a left-child (denoted by 1.left) and a right-child (denoted by s.right). The left/right children can be mull. If the left (resp. right) child is non-null, then 2.left.key St.key (resp. 1.right key > 1.key). Someone has swapped the left and right children of certain nodes, resulting in a binary tree T'. You are given the root of T'. Explain in words (no pseudocode) how to recover the original tree T given T', using only o(n) additional space. No partial credit for using A(n) additional space. You must include an argument for the correctness of your method and an analysis of the space used