_426. Convert Binary Search Tree to Sorted Doubly Linked List.md

426. Convert Binary Search Tree to Sorted Doubly Linked List

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 12, 2024

Last updated : July 01, 2024

---

Related Topics : Linked List, Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree, Doubly-Linked List

Acceptance Rate : 65.02 %

---

Solutions

• m426 v1 External Array.py

Python

m426 v1 External Array.py

"""
# 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 root

        nodes = {}
        toVisit = [root]
        while toVisit :
            curr = toVisit.pop()
            if not curr :
                continue

            nodes[curr.val] = curr
            toVisit.append(curr.left)
            toVisit.append(curr.right)
        
        nodeVals = sorted(nodes.keys())
        output = nodes.get(nodeVals[0])
        
        for i in range(len(nodeVals)) :
            nodes[nodeVals[i]].right = nodes[nodeVals[(i + 1) % len(nodeVals)]]
            nodes[nodeVals[i]].left = nodes[nodeVals[(i - 1 + len(nodeVals)) % len(nodeVals)]]
        
        return output