FastPrepConvert a Binary Tree to a Doubly Linked List
Problems/Convert a Binary Tree to a Doubly Linked List

Convert a Binary Tree to a Doubly Linked List

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The source requires in-order conversion and reuse of left/right as previous/next. Indexed node rows and the returned head-order observation are practice interface choices. Estimated match95%.

Node i is the row nodes[i]=[value,leftID,rightID], with -1 denoting a missing child. When nonempty, the tree root is node 0.

Convert the original tree to a noncircular doubly linked list in its in-order traversal order. Reuse the original node records: overwrite each leftID with the previous node ID and each rightID with the next node ID. Values and node identities must be preserved; the tree need not be a search tree.

Return the list from head to tail as rows [nodeID,value,previousID,nextID]. The head previousID and tail nextID are -1. Empty input returns []. This output observes the in-place links and preserves identity even when values repeat.

Function

treeToDoublyList(nodes: int[][]) → int[][]

Examples

Example 1

nodes = [[4,1,2],[2,3,4],[6,-1,-1],[1,-1,-1],[3,-1,-1]]return = [[3,1,-1,1],[1,2,3,4],[4,3,1,0],[0,4,4,2],[2,6,0,-1]]

Original in-order IDs are 3,1,4,0,2. The output preserves these IDs and wires their previous/next links.

Example 2

nodes = [[7,-1,-1]]return = [[0,7,-1,-1]]

The only node is both head and tail.

Constraints

  • 0 <= nodes.length <= 500.
  • Each row has exactly 3 entries.
  • -1000000000 <= every table entry <= 1000000000.
  • Each child ID is -1 or a valid row index. When nonempty, node 0 is the root of a valid binary tree containing every row exactly once.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • BST to Sorted Circular Doubly Linked ListGoogle · ONSITE INTERVIEWGoogle interview questions
  • BST to Sorted Circular Doubly Linked ListApple · ONSITE INTERVIEWApple interview questions
  • BST to Sorted Circular Doubly Linked ListBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Convert a BST to a Doubly Linked ListMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Turn a BST Into a Sorted Doubly Linked ListAdobe · PHONE SCREENAdobe interview questions
  • Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
  • Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
  • JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
  • Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
  • Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions

Interview reports that mention this question

  • Expedia New Grad SDE Earlier Loops: 5 Experiences (Part 2 of 3)
  • Expedia New Grad SDE Interviews: 20 Experiences (Part 1 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[][] treeToDoublyList(int[][] nodes) {
        // Write your code here.
    }

}
Checking account…