Company: Media_Net__SDE_17nov
Difficulty: medium
Recover Binary Search Tree Problem Description Two elements of a binary search tree (BST) are swapped by mistake. Tell us the 2 values swapping which the tree will be restored. Follow-up Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? For your reference, the definition for a binary tree node is: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ The function signature is: vector Solution::recoverTree(TreeNode* A) Examples Example 1: Input: 1 / \ 2 3 Output: [1, 2] Explanation: Swapping 1 and 2 will change the BST to be 2 / \ 1 3 which is a valid BST