⚡Flashcard Drill➔
NeetCode #470LC-426MediumTrees
← Back to All Problems

#470 · #426 · Convert Binary Search Tree to Sorted Doubly Linked List(将二叉搜索树转化为排序的双向链表)

📌 Problem Statement & Constraints

Convert a binary search tree into a sorted circular doubly linked list in place, where left is the predecessor and right is the successor. Return the smallest value's node. Constraints: the number of nodes is in [0, 2000], -1000 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. An in-order traversal visits the nodes in ascending order, which is exactly the linked-list order.
  2. During the traversal, link each node's left to the previous node and the previous node's right to it.
  3. Remember the first node visited; at the end, close the circle by linking the first and last.
  4. The traversal is O(n) and the relinking happens in place.

💻 Benchmark Python3 Implementation

class Solution:
    def treeToDoublyList(self, root: "Optional[Node]") -> "Optional[Node]":
        if not root:
            return None
        self.first = None
        self.last = None

        def inorder(node: "Optional[Node]") -> None:
            if not node:
                return
            inorder(node.left)
            if self.last:
                self.last.right = node     # successor link
                node.left = self.last      # predecessor link
            else:
                self.first = node          # the smallest node
            self.last = node
            inorder(node.right)

        inorder(root)
        # close the circle
        self.first.left = self.last
        self.last.right = self.first
        return self.first

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to close the circle: the list must be circular, so the first and last nodes must be linked both ways.
  • Setting first at every node: it must be set only for the very first (smallest) node.
  • Linking before recursing into the left subtree: the in-order order is what makes the links sorted.
  • Assuming the tree is non-empty: an empty tree must return None.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems