Skip to content

426. Convert Binary Search Tree to Sorted Doubly Linked List 👍

Approach 1: Divide and conquer

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  Node* treeToDoublyList(Node* root) {
    if (root == nullptr)
      return nullptr;
    Node* leftHead = treeToDoublyList(root->left);
    Node* rightHead = treeToDoublyList(root->right);
    root->left = root;
    root->right = root;
    return connect(connect(leftHead, root), rightHead);
  }

 private:
  Node* connect(Node* node1, Node* node2) {
    if (node1 == nullptr)
      return node2;
    if (node2 == nullptr)
      return node1;

    Node* tail1 = node1->left;
    Node* tail2 = node2->left;

    // Connect node1's tail with node2.
    tail1->right = node2;
    node2->left = tail1;

    // Connect node2's tail with node1.
    tail2->right = node1;
    node1->left = tail2;
    return node1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public Node treeToDoublyList(Node root) {
    if (root == null)
      return null;
    Node leftHead = treeToDoublyList(root.left);
    Node rightHead = treeToDoublyList(root.right);
    root.left = root;
    root.right = root;
    return connect(connect(leftHead, root), rightHead);
  }

  private Node connect(Node node1, Node node2) {
    if (node1 == null)
      return node2;
    if (node2 == null)
      return node1;

    Node tail1 = node1.left;
    Node tail2 = node2.left;

    // Connect node1's tail with node2.
    tail1.right = node2;
    node2.left = tail1;

    // Connect node2's tail with node1.
    tail2.right = node1;
    node1.left = tail2;
    return node1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def treeToDoublyList(self, root: 'Node | None') -> 'Node | None':
    if not root:
      return None
    leftHead = self.treeToDoublyList(root.left)
    rightHead = self.treeToDoublyList(root.right)
    root.left = root
    root.right = root
    return self._connect(self._connect(leftHead, root), rightHead)

  def _connect(self, node1: 'Node | None', node2: 'Node | None') -> 'Node | None':
    if not node1:
      return node2
    if not node2:
      return node1

    tail1 = node1.left
    tail2 = node2.left

    # Connect node1's tail with node2.
    tail1.right = node2
    node2.left = tail1

    # Connect node2's tail with node1.
    tail2.right = node1
    node1.left = tail2
    return node1

Approach 2: Stack

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  // Similar to 94. Binary Tree Inorder Traversal
  Node* treeToDoublyList(Node* root) {
    if (root == nullptr)
      return nullptr;

    stack<Node*> stack;
    Node* first = nullptr;
    Node* pred = nullptr;

    while (root != nullptr || !stack.empty()) {
      while (root != nullptr) {
        stack.push(root);
        root = root->left;
      }
      root = stack.top(), stack.pop();
      if (first == nullptr)
        first = root;
      if (pred != nullptr) {
        pred->right = root;
        root->left = pred;
      }
      pred = root;
      root = root->right;
    }

    pred->right = first;
    first->left = pred;
    return first;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  // Similar to 94. Binary Tree Inorder Traversal
  public Node treeToDoublyList(Node root) {
    if (root == null)
      return null;

    Deque<Node> stack = new ArrayDeque<>();
    Node first = null;
    Node pred = null;

    while (root != null || !stack.isEmpty()) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (first == null)
        first = root;
      if (pred != null) {
        pred.right = root;
        root.left = pred;
      }
      pred = root;
      root = root.right;
    }

    pred.right = first;
    first.left = pred;
    return first;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def treeToDoublyList(self, root: 'Node | None') -> 'Node | None':
    if not root:
      return None

    stack = []
    first = None
    pred = None

    while root or stack:
      while root:
        stack.append(root)
        root = root.left
      root = stack.pop()
      if not first:
        first = root
      if pred:
        pred.right = root
        root.left = pred
      pred = root
      root = root.right

    pred.right = first
    first.left = pred
    return first