Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

426. Convert Binary Search Tree to Sorted Doubly Linked List

Time: $O(n)$

Space: $O(h)$

			


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




			


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




			


class Solution {
 public:
  // Very simliar 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;
  }
};