426. Convert Binary Search Tree to Sorted Doubly Linked List

solution.py

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

# return pointer to leftmost element
# create fake head
# find smallest element with DFS -> connect to head


"""

class Solution:
    def __init__(self):
        self.left_most_node = None
        
    def in_order(self, root, prev):
        if not root:
            return
        
        left = self.in_order(root.left, root)
        right = self.in_order(root.right, root)
    
        
        if not left and not right:
            if not self.left_most_node:
                print(f"assign left most aka smallest node {root.val}")
                self.left_most_node = root
            return root
        
        print(f"-- current root is {root.val}, prev is {prev.val}, left is {left.val if left else None}, right is {right.val if right else None} --")
        
        # previous node should point to the right node instead of root 
        prev.left = right
        
        if right:
            # right should point to the root
            right.left = root
        
        
        print(f"Previous node: {prev.val}, previous node prev: {prev.left.val}, root: {root.val}, root prev: {root.left.val}, root next: {root.right.val}")
        
        return prev
        
        

        
    
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        dummy_node = TreeNode(val="blah")
        
        prev = self.in_order(root, dummy_node)
        
        # left of the previous is the rightmost node
        # lets point leftmost node next to rightmost node
        
        self.left_most_node.right = prev.left
        
        # now lets point rightmost mode next (aka right) to leftmost node
        
        prev.left.right = self.left_most_node
        
        
        return self.left_most_node