Leetcode

Convert Binary Search Tree to Sorted Doubly Linked List

May 26, 2022 by aAshish

Approach 1: Divide and conquer

  • Time:O(n)
  • Space:O(h)

C++

 
class Solution {
 public:
  Node* treeToDoublyList(Node* root) {
    if (!root)
      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)
      return node2;
    if (!node2)
      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;
  }
};

JAVA

 
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)

C++

 
class Solution {
 public:
  Node* treeToDoublyList(Node* root) {
    // very similar to 94. Binary Tree Inorder Traversal
    if (!root)
      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)
        first = root;
      if (pred) {
        pred->right = root;
        root->left = pred;
      }
      pred = root;
      root = root->right;
    }

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

JAVA

 
class Solution {
  public Node treeToDoublyList(Node root) {
    // very similar to 94. Binary Tree Inorder Traversal
    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;
  }
}