Leetcode 426

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        
        stack = []

        dummyHead = Node(None)
        headNode = dummyHead

        while True:
            if root:
                stack.append(root)
                root = root.left
            elif stack:
                currentNode = stack.pop()
                # process the currentNode
                dummyHead.right = currentNode
                currentNode.left = dummyHead
                dummyHead = dummyHead.right

                lastNode = currentNode
                root = currentNode.right
            else:
                break

        # link the right of the headNode (firstNode) to lastNode
        firstNode = headNode.right
        firstNode.left = lastNode
        lastNode.right = firstNode

        return firstNode