Link a Binary Tree in Spiral Order
Updated
Problem statement
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 <= 500nodes[i].length == 3-10^4 <= nodes[i][0] <= 10^4- Each child ID
nodes[i][1]andnodes[i][2]is -1 or a valid row index. - When
nodesis 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)