Convert Binary Search Tree to Sorted Doubly Linked List

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	25 MB
Date	2020-01-13

Solution

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

    public Node() {}

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

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
*/
public class Solution {
    public Node TreeToDoublyList(Node root) {
            if (root == null)
    {
        return null;
    }

    Node cur = root;
    Node start = null;

    Node prev = null;
    Stack<Node> st = new Stack<Node>();
    while (st.Count != 0 || cur != null)
    {
        while (cur != null)
        {
            st.Push(cur);
            cur = cur.left;
        }

        cur = st.Pop();
        if( start == null) start = cur;
        if (prev != null)
        {
            prev.right = cur;
            cur.left = prev;
        }
        prev = cur;
        cur = cur.right;
    }
    start.left = prev;
    prev.right = start;
    return start;
}
}

📜 1 more C# submission(s)

Submission (2020-01-13) — 100 ms, 25 MB

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

    public Node() {}

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

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
*/
public class Solution {
    public Node TreeToDoublyList(Node root) {
            if (root == null)
    {
        return null;
    }

    Node cur = root;
    Node start = null;

    Node prev = null;
    Stack<Node> st = new Stack<Node>();
    while (st.Count != 0 || cur != null)
    {
        while (cur != null)
        {
            st.Push(cur);
            cur = cur.left;
        }

        cur = st.Pop();
        if( start == null) start = cur;
        if (prev != null)
        {
            prev.right = cur;
            cur.left = prev;
        }
        prev = cur;
        cur = cur.right;
    }
    start.left = prev;
    prev.right = start;
    return start;
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed