FastPrepBinary Tree Zigzag Traversal
Problems/Binary Tree Zigzag Traversal

Binary Tree Zigzag Traversal

Expedia logoExpedia● MediumNEW GRADINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report names zigzag tree traversal. We made the function interface clear: tree rows with indexes, the result as one flat list in the returned order, and input limits. Our version is about 95% the same as the reported question.

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 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

  • 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

Interview reports that mention this question

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia New Grad SDE Earlier Loops: 5 Experiences (Part 2 of 3)

Expedia interview experiences

  • 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[] zigzagTraversal(int[][] nodes) {
        // Write your code here.
    }

}
Checking account…