Update Convert Binary Search Tree to Sorted Doubly Linked List.java

varunu28 · web-flow · commit 2e8bd9e98c42 · 2022-04-05T19:46:25.000+05:30
diff --git a/Medium/Convert Binary Search Tree to Sorted Doubly Linked List.java b/Medium/Convert Binary Search Tree to Sorted Doubly Linked List.java
@@ -20,27 +20,35 @@ public Node(int _val,Node _left,Node _right) {
 */
 
 class Solution {
-  Node prev;
   public Node treeToDoublyList(Node root) {
     if (root == null) {
       return root;
     }
-    Node dummy = new Node(0);
-    prev = dummy;
-    helper(root);
-    prev.right = dummy.right;
-    dummy.right.left = prev;
-    return dummy.right;
-  }
-  
-  private void helper(Node root) {
-    if (root == null) {
-      return;
+    Stack<Node> stack = new Stack<>();
+    while (root != null) {
+      stack.push(root);
+      root = root.left;
+    }
+    Node head = null;
+    Node prev = null;
+    while (!stack.isEmpty()) {
+      Node removed = stack.pop();
+      Node rightNode = removed.right;
+      while (rightNode != null) {
+        stack.push(rightNode);
+        rightNode = rightNode.left;
+      }
+      if (head == null) {
+        head = removed;
+      }
+      if (prev != null) {
+        prev.right = removed;
+      }
+      removed.left = prev;
+      prev = removed;
     }
-    helper(root.left);
-    prev.right = root;
-    root.left = prev;
-    prev = root;
-    helper(root.right); 
+    head.left = prev;
+    prev.right = head;
+    return head;
   }
 }
