FastPrepLink a Binary Tree in Spiral Order
Problems/Link a Binary Tree in Spiral Order

Link a Binary Tree in Spiral Order

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a post from August 2021 about Expedia's on-campus intern hiring for summer 2022 internships. The post names this task in the first technical interview.

The post does not define spiral order or give a tree format, examples or limits. We chose these: spiral order is the root, then depth 1 from right to left, with the direction changing at each deeper level. The tree is a table of [value, leftID, rightID] rows, with up to 500 nodes and values from -10^4 to 10^4. The left and right slots are reused as previous and next links. The list is returned as [nodeID, value, previousID, nextID] rows from head to tail. Only those rows are checked, not whether the table was changed in place.

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

A binary tree is given as a table nodes. Row i is node i and holds [value, leftID, rightID], where an ID of -1 means there is no child. When the table is not empty, node 0 is the root.

Turn the tree into a doubly linked list in spiral order: first the root (depth 0), then the nodes at depth 1 from right to left, then the nodes at depth 2 from left to right, and so on, changing direction at every depth.

Build the list in place by reusing the rows: in each row, overwrite leftID with the ID of the previous node in the list and rightID with the ID of the next node. The head's previous ID and the tail's next ID are -1.

Return the list from head to tail as rows [nodeID, value, previousID, nextID], one row per node. Return [] for an empty table. Node IDs are returned, not just values, so the answer is exact even when values repeat. Only the returned rows are checked. The tests cannot see whether you changed the table itself.

Function

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

Examples

Example 1

nodes = [[10,3,1],[30,-1,2],[50,-1,-1],[20,4,-1],[40,-1,-1]]return = [[0,10,-1,1],[1,30,0,3],[3,20,1,4],[4,40,3,2],[2,50,4,-1]]

Depth 0 is the root, node 0. Depth 1 holds node 3 (left) and node 1 (right); it is read right to left, so node 1 comes before node 3. Depth 2 holds node 4 (under node 3) and node 2 (under node 1); it is read left to right: node 4, then node 2. The list is 0, 1, 3, 4, 2, and each row shows its previous and next node IDs.

Example 2

nodes = [[5,1,2],[5,3,4],[5,5,-1],[8,6,-1],[8,-1,-1],[8,-1,7],[9,-1,-1],[9,-1,-1]]return = [[0,5,-1,2],[2,5,0,1],[1,5,2,3],[3,8,1,4],[4,8,3,5],[5,8,4,7],[7,9,5,6],[6,9,7,-1]]

Depth 1 from right to left is node 2, then node 1. Depth 2 from left to right is nodes 3, 4, 5. Depth 3 holds node 6 (under node 3) and node 7 (under node 5); from right to left that is node 7, then node 6. Many values repeat, so only the node IDs show which node is where.

Example 3

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

A single node is both the head and the tail, so its previous and next IDs are both -1.

Constraints

  • 0 <= nodes.length <= 500
  • nodes[i].length == 3
  • -10^4 <= nodes[i][0] <= 10^4
  • Each child ID nodes[i][1] and nodes[i][2] is -1 or a valid row index.
  • When nodes is not empty, node 0 is the root of one binary tree that contains 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

  • Linked List of Binary Tree Nodes at a Given LevelBloomberg LP · PHONE SCREENBloomberg LP interview questions
  • Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
  • Binary Tree Spiral Level OrderAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Zigzag Level-Order TraversalFlipkart · ONSITE INTERVIEW
  • Binary Tree Zigzag Level Order TraversalLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
  • Sorted Doubly Linked List to Balanced BST In PlaceSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Binary Tree Nodes at Distance KApple · ONSITE INTERVIEWApple interview questions
  • Binary Tree Zigzag Level Order TraversalMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Bottom View of a Binary TreeOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
  • Find the Tree DiameterAdyen · ONSITE INTERVIEWAdyen interview questions

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)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[][] treeToSpiralList(int[][] nodes) {
        // Write your code here.
    }
}
Checking account…