Sponsored
Sponsored
This approach involves performing an in-order traversal to visit the nodes of the tree in sorted order. As we visit each node, we rearrange the nodes to form a new tree where each node only has a right child.
We will use a dummy node that helps us easily chain the nodes in the desired manner. During the traversal, we append each node to the right of the previous node.
Time Complexity: O(n), where n is the number of nodes, as we visit each node once.
Space Complexity: O(n), due to the recursion stack space where n is the number of nodes.
1struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};
7
8class Solution {
9public:
10 TreeNode* increasingBST(TreeNode* root) {
11 TreeNode* dummy = new TreeNode(0);
12 TreeNode* cur = dummy;
13 inorder(root, cur);
14 return dummy->right;
15 }
16
17private:
18 void inorder(TreeNode* node, TreeNode*& cur) {
19 if (!node) return;
20 inorder(node->left, cur);
21 node->left = nullptr;
22 cur->right = node;
23 cur = node;
24 inorder(node->right, cur);
25 }
26};The C++ solution defines a Solution class with a private helper method inorder that is used to traverse and reconstruct the tree. We maintain a current pointer cur which is always set to point to the last added node. We make sure to nullify the left pointers of each node before attaching them to the right of the current pointer.
A space-optimized approach to perform in-order traversal without recursion or a stack is Morris Traversal. This involves temporarily modifying the tree structure by linking the in-order predecessor of each node to the node itself, allowing us to traverse the tree without additional space.
During the traversal, we reconstruct the tree in the desired form by altering the left and right pointers.
Time Complexity: O(n), as each node is processed a constant number of times (at most twice).
Space Complexity: O(1), as we are not using any extra space other than a couple of pointers.
The Python solution employs Morris Traversal to achieve O(1) space complexity. We use a while loop to traverse the tree while altering the pointers as described. When there's a left subtree, we find the predecessor, link it, and then follow the same logic until the tree is reconstructed in the desired order.