Encode and Rebuild a Binary Tree
Company: Apple
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Design two functions for a binary tree:
- `encode(root) -> string`
- `decode(data) -> root`
Each tree node contains an integer value and has up to two children.
Your `encode` function should convert a binary tree into a string representation. Your `decode` function should reconstruct an equivalent binary tree from that string.
Requirements:
- The reconstructed tree must have the same structure and node values as the original tree.
- The format may be any deterministic representation of your choice.
- Empty children must be represented in a way that allows exact reconstruction.
- You may assume node values fit in standard integer range.
Explain the data format you use and implement both functions.
Overview: This question evaluates skills in data structure serialization and deserialization, binary tree representation, and algorithmic design for deterministic data formats.
Design two binary-tree functions: encode(root) -> string and decode(data) -> root. The goal is to convert a binary tree into a deterministic string and then rebuild an equivalent tree from that string.
For this challenge, the input tree is given as a level-order Python list where None represents a missing child. Inside your solution, implement:
- encode(root): serialize the tree using preorder traversal
- decode(data): rebuild the tree from that serialized form
Use this exact deterministic format:
- Visit nodes in preorder: node, left subtree, right subtree
- Separate tokens with commas
- Use '#' to represent a null child
Example:
Tree [1, 2, 3, None, 4] becomes '1,2,#,4,#,#,3,#,#'.
For automated checking, your function should:
1. Build the tree from the input level-order list
2. Encode it into a string
3. Decode the string back into a tree
4. Return a tuple: (encoded_string, rebuilt_tree_as_trimmed_level_order_list)
The rebuilt tree must match the original tree in both structure and node values.
Constraints
- 0 <= number of actual tree nodes <= 10^4
- Each node value is an integer in the standard 32-bit signed range
- The input list uses level-order representation with None for missing children
- The returned level-order list should not contain unnecessary trailing None values
Examples
Input: ([1, 2, 3, None, 4, 5],)
Expected Output: ('1,2,#,4,#,#,3,5,#,#,#', [1, 2, 3, None, 4, 5])
Explanation: Preorder with null markers is 1,2,#,4,#,#,3,5,#,#,#. Decoding that string rebuilds the same tree.
Input: ([],)
Expected Output: ('#', [])
Explanation: An empty tree is encoded as a single null marker '#', and decoding it gives back an empty tree.
Hints
- A traversal by itself is not enough to rebuild the exact tree unless you also record missing children.
- While decoding preorder data, think of each node as having two child slots to fill; a stack can help track whether the next token belongs to the left or right side.