Skip to main content
Talentd

Convert Binary Search Tree to Sorted Doubly Linked List - Solution & Explanation

MediumPremiumFree on FleetCodeLinked ListStackTreeDepth-First Search6 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

 

Example 1:

Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

Input: root = [2,1,3]
Output: [1,2,3]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
  • All the values of the tree are unique.

Approach Overview

Problem Overview: You’re given the root of a binary search tree. The task is to convert it into a sorted circular doubly linked list in-place. The in-order sequence of the BST must become the order of nodes in the doubly linked list, and the first and last nodes should be connected to make the list circular.

Approach 1: Inorder Traversal + Array (O(n) time, O(n) space)

The simplest way to think about this problem is to first collect nodes in sorted order using an inorder traversal of the BST. Store each visited node in an array. Once traversal finishes, iterate through the array and connect adjacent nodes using left and right pointers to form the doubly linked list. Finally connect the first and last nodes to make the structure circular. This approach is easy to implement but uses extra memory proportional to the number of nodes.

Approach 2: Recursive Inorder DFS (O(n) time, O(h) space)

A more optimal solution links nodes directly during an inorder traversal. Since a BST’s inorder traversal produces nodes in sorted order, maintain two pointers: prev for the previously processed node and head for the smallest node. During DFS, connect prev.right to the current node and current.left to prev. After traversal completes, connect the head and the last node to make the list circular. This method uses recursion from depth-first search and only requires the call stack.

Approach 3: Iterative Inorder with Stack (O(n) time, O(h) space)

If recursion depth is a concern, perform the same inorder traversal iteratively using a stack. Push nodes while moving left, pop to process them in sorted order, and then move to the right subtree. Each popped node is linked with the previously processed node exactly like the recursive solution. The resulting doubly linked list is formed incrementally while traversing the tree.

Approach 4: Morris Traversal (O(n) time, O(1) space)

Morris traversal removes the need for recursion or a stack by temporarily modifying tree pointers to simulate the call stack. As nodes are visited in inorder order, link them directly into the doubly linked list using the same prev pointer technique. After traversal, connect the head and tail to complete the circular list. This achieves constant auxiliary space while preserving the sorted order.

Recommended for interviews: The recursive inorder DFS approach is usually expected. It demonstrates understanding of BST properties and how inorder traversal yields sorted order. Starting with the array-based method shows clear reasoning, but linking nodes during traversal proves stronger algorithmic skill and space optimization.

Solution

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Inorder Traversal + ArrayO(n)O(n)Simplest implementation when extra memory is acceptable
Recursive Inorder DFSO(n)O(h)Common interview solution using recursion and BST inorder property
Iterative Inorder with StackO(n)O(h)Avoid recursion when stack depth may be large
Morris TraversalO(n)O(1)Best when constant extra space is required

Video Solution

CONVERT BINARY SEARCH TREE TO SORTED DOUBLY LINKED LIST | LEETCODE # 426 | PYTHON SOLUTION • Cracking FAANG • 28,913 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Convert Binary Search Tree to Sorted Doubly Linked List easy or hard?
The problem is generally classified as Medium difficulty. Understanding that inorder traversal of a BST produces sorted order is the key insight, while correctly linking nodes into a circular doubly linked list requires careful pointer handling.
Convert Binary Search Tree to Sorted Doubly Linked List Python/Java solution
The typical implementation performs an inorder DFS and links nodes while traversing. Maintain two references: prev for the previous node and head for the smallest node. This approach works identically across Python, Java, C++, Go, and JavaScript with O(n) time complexity.
How to solve Convert Binary Search Tree to Sorted Doubly Linked List in O(n)?
Perform an inorder traversal of the BST and maintain a pointer to the previously visited node. For each node, connect prev.right to the current node and current.left to prev. After traversal finishes, connect the smallest node (head) and the largest node (tail) to make the doubly linked list circular.
What is the best approach for Convert Binary Search Tree to Sorted Doubly Linked List?
The most common approach is inorder traversal with pointer linking. A Binary Search Tree produces nodes in sorted order during inorder traversal, so you can connect each visited node with the previous one to form a doubly linked list. This runs in O(n) time and O(h) space where h is the tree height due to recursion stack.
Is Convert Binary Search Tree to Sorted Doubly Linked List asked at Google/Amazon/Meta?
BST transformation and inorder traversal problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include converting BST to linked list, flattening trees, or building sorted structures using inorder traversal.
What data structure is used in Convert Binary Search Tree to Sorted Doubly Linked List?
The problem primarily uses a Binary Search Tree and converts it into a doubly linked list. The algorithm often relies on inorder traversal using recursion, a stack, or Morris traversal while maintaining previous and head pointers.
What is the time complexity of Convert Binary Search Tree to Sorted Doubly Linked List?
All optimal solutions traverse every node exactly once, giving O(n) time complexity where n is the number of nodes in the BST. Space complexity is O(h) for recursive or stack-based inorder traversal, and O(1) if Morris traversal is used.

Ready to solve this problem?

Practice Convert Binary Search Tree to Sorted Doubly Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal