Convert Binary Search Tree to Sorted Doubly Linked List solution and explanation
9 more videos on this problem
CONVERT BINARY SEARCH TREE TO SORTED DOUBLY LINKED LIST | LEETCODE # 426 | PYTHON SOLUTIONCracking FAANG · 18:21 · 28K views
[Java] Leetcode 426. Convert Binary Search Tree to Sorted Doubly Linked List [Binary Search Tree #6]Eric Programming · 8:08 · 6K views
LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List Explanation and Solutionhappygirlzt · 4:08 · 4K views
Leetcode 426 Convert Binary Search Tree to Sorted Doubly Linked ListRen Zhang · 15:23 · 2K views
Amazon Coding Interview Question | Leetcode 426 | Convert BST to Sorted Doubly Linked ListWorkWithGoogler · 14:54 · 1K views
Leetcode 426 - Convert Binary Search Tree To Sorted Doubly Linked List (JAVA Solution Explained!)LC Bear · 10:55 · 704 views
LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked ListcoderZ · 10:11 · 559 views
Convert Binary Search Tree to Sorted Doubly Linked List || Leetcode 426constantinirimia · 11:29 · 478 views
leetcode - Convert Binary Search Tree to Sorted Doubly Linked ListBob Wei · 10:28 · 421 views
Leetcode 426 | Binary Search Tree to Doubly Linked ListRed Black Tech · 9:36 · 370 views
The problem
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
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
def dfs(root):
if root is None:
return
nonlocal prev, head
dfs(root.left)
if prev:
prev.right = root
root.left = prev
else:
head = root
prev = root
dfs(root.right)
if root is None:
return None
head = prev = None
dfs(root)
prev.right = head
head.left = prev
return head/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
private Node prev;
private Node head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
prev = null;
head = null;
dfs(root);
prev.right = head;
head.left = prev;
return head;
}
private void dfs(Node root) {
if (root == null) {
return;
}
dfs(root.left);
if (prev != null) {
prev.right = root;
root.left = prev;
} else {
head = root;
}
prev = root;
dfs(root.right);
}
}/*
// 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* prev;
Node* head;
Node* treeToDoublyList(Node* root) {
if (!root) return nullptr;
prev = nullptr;
head = nullptr;
dfs(root);
prev->right = head;
head->left = prev;
return head;
}
void dfs(Node* root) {
if (!root) return;
dfs(root->left);
if (prev) {
prev->right = root;
root->left = prev;
} else
head = root;
prev = root;
dfs(root->right);
}
};/**
* // Definition for a Node.
* function Node(val, left, right) {
* this.val = val;
* this.left = left;
* this.right = right;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var treeToDoublyList = function (root) {
if (!root) return root;
let prev = null;
let head = null;
function dfs(root) {
if (!root) return;
dfs(root.left);
if (prev) {
prev.right = root;
root.left = prev;
} else {
head = root;
}
prev = root;
dfs(root.right);
}
dfs(root);
prev.right = head;
head.left = prev;
return head;
};/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* }
*/
func treeToDoublyList(root *Node) *Node {
if root == nil {
return root
}
var prev, head *Node
var dfs func(root *Node)
dfs = func(root *Node) {
if root == nil {
return
}
dfs(root.Left)
if prev != nil {
prev.Right = root
root.Left = prev
} else {
head = root
}
prev = root
dfs(root.Right)
}
dfs(root)
prev.Right = head
head.Left = prev
return head
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal + Array | O(n) | O(n) | Simplest implementation when extra memory is acceptable |
| Recursive Inorder DFS | O(n) | O(h) | Common interview solution using recursion and BST inorder property |
| Iterative Inorder with Stack | O(n) | O(h) | Avoid recursion when stack depth may be large |
| Morris Traversal | O(n) | O(1) | Best when constant extra space is required |
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.