Turn a BST Into a Sorted Doubly Linked List
Updated
Problem statement
Given the root of a binary search tree, turn its nodes into a sorted doubly linked list in place. In the list, each node's left pointer points to the previous node (the next smaller value) and its right pointer points to the next node (the next larger value). The smallest node is the head, with left set to null, and the largest node is the tail, with right set to null. Do not create new nodes.
Return the values of the list from head to tail, found by following the right pointers from the head. The judge checks only these values, so it cannot tell whether the pointers were really changed; the editorial shows how to change them.
Function
bstToSortedList(root: TreeNode) → List<Integer>Examples
Example 1
root = [8,3,12,1,6,null,15]return = [1,3,6,8,12,15]Reading the tree from left to right gives 1, 3, 6, 8, 12, 15. In the list, 1 is the head, each node's right pointer leads to the next larger value, and 15 is the tail.
Example 2
root = [5,null,9,7]return = [5,7,9]5 has only a right child 9, and 9 has a left child 7. In order: 5, 7, 9.
Example 3
root = []return = []An empty tree gives an empty list.
Constraints
- The tree has
0to500nodes. -10^4 <= Node.val <= 10^4, and all values are different.- The tree is a valid binary search tree: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Kth Smallest Value in a BSTExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- Kth Smallest Element in a BSTNutanix · PHONE SCREENNutanix interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Binary Tree Preorder TraversalMorgan Stanley · PHONE SCREENMorgan Stanley interview questions
- Binary Tree Inorder TraversalBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions
- Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions