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.
In the Python solution, we define a helper function inorder that performs an in-order traversal. We pass each node to this function to rearrange the nodes by severing the left child and linking the nodes to the right child of the current node pointed by self.cur.
The dummy node acts as a placeholder to return the new root of the tree.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def increasingBST(root: TreeNode) -> TreeNode:
8 dummy = TreeNode()
9 cur = dummy
10 node = root
11
12 while node:
13 if node.left:
14 pred = node.left
15 while pred.right and pred.right != node:
16 pred = pred.right
17 if not pred.right:
18 pred.right = node
19 node = node.left
20 else:
21 pred.right = None
22 cur.right = node
23 cur = cur.right
24 node = node.right
25 else:
26 cur.right = node
27 cur = cur.right
28 node = node.right
29
30 return dummy.rightThe 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.