Binary Tree Zigzag Traversal
Updated
Problem statement
Return the values of a binary tree in zigzag level order: read the root level from left to right, the next level from right to left, and keep alternating direction at every depth. Flatten all levels into one returned array.
For this exercise, row i of nodes identifies node i and contains [value, leftChildId, rightChildId]. A child ID of -1 means null. Node 0 is the root when the table is nonempty. An empty table returns an empty array.
Function
zigzagTraversal(nodes: int[][]) → int[]Examples
Example 1
nodes = [[1,1,2],[2,3,4],[3,5,6],[4,-1,-1],[5,-1,-1],[6,-1,-1],[7,-1,-1]]return = [1,3,2,4,5,6,7]Depth 0 contributes [1]. Depth 1 is read right-to-left as [3,2]. Depth 2 is read left-to-right as [4,5,6,7].
Example 2
nodes = [[8,2,1],[4,3,-1],[6,-1,4],[2,-1,-1],[7,-1,-1]]return = [8,4,6,7,2]The second level contains values [6,4] from left to right, so it contributes [4,6]. The next level contributes [7,2] from left to right.
Example 3
nodes = []return = []There is no root and no value to visit.
Constraints
0 <= nodes.length <= 500.- Each row has exactly
3entries. -1000000000 <= every table entry <= 1000000000.- Each child ID is -1 or a valid row index. When nonempty, node
0is 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
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Binary Tree Spiral Level OrderAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Binary Tree Spiral Level OrderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Top View of a Binary TreeInMobi · ONSITE INTERVIEWInMobi interview questions
- Maximum Value at Each Tree LevelMeta · ONSITE INTERVIEWMeta interview questions
- Maximum Depth of Binary TreeLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Symmetric Binary TreeFigma · ONSITE INTERVIEWFigma interview questions
- Mirror a Binary TreeAMD · ONSITE INTERVIEWAMD interview questions
- Vertical Order Traversal of a Binary TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions