FastPrepTurn a BST Into a Sorted Doubly Linked List
Problems/Turn a BST Into a Sorted Doubly Linked List

Turn a BST Into a Sorted Doubly Linked List

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This problem rearranges the nodes of a binary search tree into a sorted doubly linked list. An Adobe CS1 report from Noida (posted March 2024, rejected) lists this as one of two coding questions in its first round. That round was held with a senior CS, after an object-oriented programming question that the candidate could not answer. The candidate says both coding questions were finished in time. The report gives no interface, limits or examples.

Our choices: left points to the previous node and right to the next. The list is not circular. The tree has 0 to 500 nodes with distinct values from -10^4 to 10^4. The examples are new. The function returns the list's values from head to tail, so we check the order but cannot see the pointers. The editorial changes them in place.

Our version is about 75% the same as the reported question.

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]
root
83161215

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]
root
597

5 has only a right child 9, and 9 has a left child 7. In order: 5, 7, 9.

Example 3

root = []return = []
root
empty

An empty tree gives an empty list.

Constraints

  • The tree has 0 to 500 nodes.
  • -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

Interview reports that mention this question

  • Adobe CS1 Interviews: 14 Experiences (Part 4 of 6)
  • Adobe Experienced Hire Interviews: 55 Experiences (Part 1 of 6)

Adobe interview experiences

  • Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
  • Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
  • Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
  • Adobe New Grad MTS Interview Questions: 7 Experiences
All Adobe interview questionsSee Adobe hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> bstToSortedList(TreeNode root) {
        // Write your code here.
    }
}
Checking account…