Serialize and Deserialize a Binary Tree
Updated
Problem statement
Implement binary-tree serialization and deserialization. This exercise uses a fixed, finite adapter treeCodec(root, encoded) that returns an integer matrix with exactly two rows.
- Row 0 is the serialization of the supplied
root. Visit the root, then its left subtree, then its right subtree. Write each node value and write-1for every missing child. The empty tree serializes to[-1]. - Deserialize the independent
encodedarray using that same preorder/null format. Row 1 is the reconstructed tree in compact level order: start at its root, visit each non-null node’s left then right child, write-1for missing child slots, and remove all trailing-1markers. An empty reconstructed tree produces an empty row.
The two inputs may describe different trees. Implement an actual decoder that rebuilds child links, then traverse the reconstructed tree for row 1. Merely serializing and returning the original tree does not implement this adapter. Duplicate node values are allowed; the null markers preserve topology. Do not modify either input or retain state between calls.
Input tree examples use null for missing slots in the TreeNode argument. The integer codec and both returned rows use -1 as specified above.
Function
treeCodec(root: TreeNode, encoded: int[]) → int[][]Examples
Example 1
root = [4,2,7]encoded = [9,-1,5,3,-1,-1,-1]return = [[4,2,-1,-1,7,-1,-1],[9,-1,5,3]]The supplied tree has root 4 with left 2 and right 7, so its preorder/null row is [4,2,-1,-1,7,-1,-1]. The independent data decodes to root 9, right child 5, and 5’s left child 3. Its compact level-order row is [9,-1,5,3].
Example 2
root = []encoded = [8,-1,-1]return = [[-1],[8]]The supplied root is empty and serializes to [-1]. The independent encoded array [8,-1,-1] reconstructs a singleton 8, whose compact level-order row is [8].
Constraints
- For this exercise, assume root is a valid finite binary tree with between 0 and 100 non-null nodes.
- Every non-null node value is between 1 and 1000, inclusive.
- For this exercise, assume 1 <= encoded.length <= 201.
- Every encoded token is between -1 and 1000, inclusive.
- encoded is exactly one valid complete preorder encoding of a finite binary tree with at most 100 non-null nodes: -1 denotes null, and every other token is a value from 1 through 1000 followed by complete left and right subtree encodings. No tokens are omitted or left over.
More Morgan Stanley Online Assessment questions
- Three-Resource 0/1 KnapsackOA · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Maximum Total of Nonadjacent RatingsOA · Seen Jul 2026
- Count Shipment SchedulesOA · Seen Apr 2026
- Delete and EarnOA · Seen Apr 2026
- Interleave Array HalvesOA · Seen Apr 2026
- Get Patch SequenceOA · Seen Feb 2025
- String Subsequences 🐳OA · Seen Mar 2024
- Binary Tree Level OrderOA · Seen Feb 2024
- Merge IntervalsOA · Seen Feb 2024
Similar questions at other companies
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Longest Transfer Time in a Server TreeRippling · OARippling interview questions
- Longest Alternating a/b Path in a TreeHudson River Trading · OAHudson River Trading interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Tree Height After Child PromotionSnowflake · PHONE SCREENSnowflake interview questions
- Binary Tree Spiral Level OrderAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Check a Complete Binary TreeGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)