Update Increasing Order Search Tree.java

varunu28 · web-flow · commit e9f848ca47be · 2022-04-17T06:49:00.000+05:30
diff --git a/Easy/Increasing Order Search Tree.java b/Easy/Increasing Order Search Tree.java
@@ -14,22 +14,26 @@
  * }
  */
 class Solution {
-  TreeNode curr;
   public TreeNode increasingBST(TreeNode root) {
-    TreeNode ans = new TreeNode(-1);
-    curr = ans;
-    inorder(root);
-    return ans.right;
-  }
-  
-  private void inorder(TreeNode node) {
-    if (node == null) {
-      return;
+    Stack<TreeNode> stack = new Stack<>();
+    while (root != null) {
+      stack.push(root);
+      root = root.left;
+    }
+    TreeNode newHead = null;
+    while (!stack.isEmpty()) {
+      TreeNode removed = stack.pop();
+      if (newHead == null) {
+        newHead = removed;
+      }
+      TreeNode rightNode = removed.right;
+      while (rightNode != null) {
+        stack.push(rightNode);
+        rightNode = rightNode.left;
+      }
+      removed.right = stack.isEmpty() ? null : stack.peek();
+      removed.left = null;
     }
-    inorder(node.left);
-    node.left = null;
-    curr.right = node;
-    curr = node;
-    inorder(node.right);
+    return newHead;
   }
 }
