How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Apple during technical interviews.

Encode and Rebuild a Binary Tree | Apple Coding Question

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.

Quick Answer: 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.

Input: ([7],)

Expected Output: ('7,#,#', [7])

Explanation: A single node has value 7 and two null children, so its encoding is 7,#,#.

Input: ([-1, -1, 2, None, -1],)

Expected Output: ('-1,-1,#,-1,#,#,2,#,#', [-1, -1, 2, None, -1])

Explanation: Negative values and duplicates must be preserved exactly in both the serialized form and the rebuilt tree.

Input: ([1, None, 2, None, 3],)

Expected Output: ('1,#,2,#,3,#,#', [1, None, 2, None, 3])

Explanation: This right-skewed tree requires null markers on each missing left child to remain reconstructible.

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.

Quick Overview

This question evaluates skills in data structure serialization and deserialization, binary tree representation, and algorithmic design for deterministic data formats.