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
33
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
31
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;
  }
}

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 || !stack.empty()) {
      while (root) {
        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;
  }
}