LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List Solution

Master LeetCode problem 426 (Convert Binary Search Tree to Sorted Doubly Linked List), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

426. Convert Binary Search Tree to Sorted Doubly Linked List

Medium

Linked List Stack Tree Depth-First Search Binary Search Tree Binary Tree Doubly-Linked List

Problem Explanation

Explanation

To convert a binary search tree (BST) to a sorted doubly linked list, we can perform an in-order traversal of the BST. During the traversal, we will maintain a pointer to the current node and update the links between nodes to create the doubly linked list.

The steps involved in the algorithm are as follows:

Perform an in-order traversal of the BST.
During the traversal, update the links between nodes to form the doubly linked list.
At the end of the traversal, the head of the doubly linked list will be the leftmost node in the BST, and the tail will be the rightmost node.

Time complexity: O(N) - where N is the number of nodes in the BST. Space complexity: O(H) - where H is the height of the BST.

Solution Code

class Solution {
    Node prev = null;
    Node head = null;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;

        inOrderTraversal(root);

        head.left = prev;
        prev.right = head;

        return head;
    }

    private void inOrderTraversal(Node node) {
        if (node == null) return;

        inOrderTraversal(node.left);

        if (prev == null) {
            head = node;
        } else {
            prev.right = node;
            node.left = prev;
        }

        prev = node;

        inOrderTraversal(node.right);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 426 (Convert Binary Search Tree to Sorted Doubly Linked List)?

This page provides optimized solutions for LeetCode problem 426 (Convert Binary Search Tree to Sorted Doubly Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 426 (Convert Binary Search Tree to Sorted Doubly Linked List)?

The time complexity for LeetCode 426 (Convert Binary Search Tree to Sorted Doubly Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 426 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 426 in Java, C++, or Python.

Back to LeetCode Solutions