---
tags: leetcode
---

# [426. Convert Binary Search Tree to Sorted Doubly Linked List](https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
DFS, recursion, inorder traversal
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
public:
    Node *treeToDoublyList(Node *root) {
        if (root == nullptr) {
            return nullptr;
        }

        head = nullptr;
        predecessor = nullptr;

        dfs(root);
        head->left = predecessor;
        predecessor->right = head;

        return head;
    }

private:
    Node *head;
    Node *predecessor;

    void dfs(Node *root) {
        if (root == nullptr) {
            return ;
        }

        dfs(root->left);

        if (head == nullptr) {
            head = root;
        }

        if (predecessor != nullptr) {
            predecessor->right = root;
            root->left = predecessor;
        }
        predecessor = root;

        dfs(root->right);
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree referred by `root`.
### Space Complexity
$O(H)$
$H$ is the height of binary tree referred by `root`.
## Solution 2
### The Key Idea for Solving This Coding Question
Morris traversal
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
public:
    Node *treeToDoublyList(Node *root) {
        if (root == nullptr) {
            return nullptr;
        }
        
        Node *head = nullptr, *predecessor = nullptr;
        while (root != nullptr) {
            if (root->left == nullptr) {
                if (head == nullptr) {
                    head = root;
                }
                
                if (predecessor != nullptr) {
                    predecessor->right = root;
                    root->left = predecessor;
                }
                predecessor = root;
                
                root = root->right;
            } else {
                Node *x = root->left;
                while (x->right != nullptr && x->right != root) {
                    x = x->right;
                }
                
                if (x->right == nullptr) {
                    x->right = root;
                    root = root->left;

                } else {
                    if (head == nullptr) {
                        head = root;
                    }
                    
                    if (predecessor != nullptr) {
                        predecessor->right = root;
                        root->left = predecessor;
                    }
                    predecessor = root;
                    
                    root = root->right;
                }
            }
        }
        
        head->left = predecessor;
        predecessor->right = head;
        
        return head;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree referred by `root`.
### Space Complexity
$O(1)$
# Miscellane
<!--
# Test Cases

[4,2,5,1,3]

[2,1,3]

[]

[1]

* Wrong Answer

[27,-99,55,null,-34,null,58,null,-8,null,59,null,8,null,68]

-->