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

## C++

``````class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root)
return nullptr;

root->left = root;
root->right = root;
}

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;

root.left = root;
root.right = root;
}

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

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