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.
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 def inorder(node):
9 if not node:
10 return
11 inorder(node.left)
12 node.left = None
13 self.cur.right = node
14 self.cur = node
15 inorder(node.right)
16
17 dummy = self.cur = TreeNode()
18 inorder(root)
19 return dummy.rightIn 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.
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.