426. Convert Binary Search Tree to Sorted Doubly Linked List

// LeetCode URL: https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
import java.util.Stack;

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

/**
 * Inorder (Recursion)
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(Height of Tree) = O(N) in worst case. (Recursion Stack)
 *
 * N = Number of nodes in the tree.
 */
class Solution1 {
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        Node dummy = new Node();
        Node[] prev = new Node[1];
        prev[0] = dummy;
        inorderHelper(root, prev);
        prev[0].right = dummy.right;
        dummy.right.left = prev[0];
        return dummy.right;
    }

    private void inorderHelper(Node node, Node[] prev) {
        if (node == null) {
            return;
        }

        inorderHelper(node.left, prev);

        prev[0].right = node;
        node.left = prev[0];
        prev[0] = node;

        inorderHelper(node.right, prev);
    }
}

/**
 * Inorder (Iterative using stack)
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(Height of Tree) = O(N) in worst case. (Stack size)
 *
 * N = Number of nodes in the tree.
 */
class Solution2 {
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        Stack<Node> stack = new Stack<>();
        Node dummy = new Node();
        Node prev = dummy;
        Node cur = root;

        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                Node temp = stack.pop();
                prev.right = temp;
                temp.left = prev;
                prev = temp;
                cur = temp.right;
            }
        }

        prev.right = dummy.right;
        dummy.right.left = prev;
        return dummy.right;
    }
}