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.
1typedef struct TreeNode {
2 int val;
3 struct TreeNode *left;
4 struct TreeNode *right;
5} TreeNode;
6
7TreeNode* newTreeNode(int val) {
8 TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
9 node->val = val;
10 node->left = node->right = NULL;
11 return node;
12}
13
14TreeNode* cur;
15
16void inorder(TreeNode* node) {
17 if (!node) return;
18 inorder(node->left);
19 node->left = NULL;
20 cur->right = node;
21 cur = node;
22 inorder(node->right);
23}
24
25TreeNode* increasingBST(TreeNode* root) {
26 TreeNode* dummy = newTreeNode(0);
27 cur = dummy;
28 inorder(root);
29 return dummy->right;
30}The C solution uses direct recursion and manual memory allocation. A global pointer cur helps track where the current node should be attached in the result list. We use a dummy node similarly to avoid handling a special case for the first node.
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.
In JavaScript, the Morris Traversal technique is applied, manipulating the tree without extra space. We iterate in a while loop, setting predecessors when necessary, allowing for in-order traversal restructuring.