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 int val;
3 TreeNode left, right;
4 TreeNode(int x) { val = x; }
5}
6
7class Solution {
8 private TreeNode cur;
9 public TreeNode increasingBST(TreeNode root) {
10 TreeNode dummy = new TreeNode(0);
11 cur = dummy;
12 inorder(root);
13 return dummy.right;
14 }
15 private void inorder(TreeNode node) {
16 if (node == null) return;
17 inorder(node.left);
18 node.left = null;
19 cur.right = node;
20 cur = node;
21 inorder(node.right);
22 }
23}In the Java version, we declare an instance variable cur to track the last node added to our restructured tree. We perform an in-order traversal with the recursive inorder method and link nodes using the right field.
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 Java solution uses the Morris Traversal method to iterate through the tree. It leverages the predecessor link creation and removal, enabling the in-order traversal without recursion or stack.