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.
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode IncreasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0);
TreeNode cur = dummy;
TreeNode node = root;
while (node != null) {
if (node.left != null) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = node;
node = node.left;
} else {
pred.right = null;
cur.right = node;
cur = cur.right;
node = node.right;
}
} else {
cur.right = node;
cur = cur.right;
node = node.right;
}
}
return dummy.right;
}
}The C# implementation efficiently transforms the BST using Morris Traversal, maintaining an O(1) space complexity. The traversal directly addresses nodes by adjusting pointers, rendering the solution usable for larger data sets in constrained environments.