Preorder stream with null markers
Ship and Restore a Sensor Tree
01. The question
Encode a binary tree in preorder with explicit null markers, reconstruct fresh nodes, and return {"encoded":[...],"decoded":[...]}. The decoded tree uses the input slot format. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Before revealing the idea, predict the result and describe what information you would need to track.
02. Worked example
Input[4,2,7]
Output{"encoded":[4,2,null,null,7,null,null],"decoded":[4,2,7]}
- Emit value, left subtree, right subtree; emit null for absent nodes.
- Decode using one shared cursor.
- Export the rebuilt tree for comparison.
Try your code
Define solve(data, parameter="") and return your result. Your code runs locally, not on a server.
Edit your test cases
Use 1-10 objects with data and an optional string parameter. Expected outputs are computed from the lesson. An optional expected field must be correct.
Input contract & reference code
Example data: [4,2,7]. Parameter: "". Numeric parameters arrive as strings; convert them with int(parameter) when needed.
The example and generated cases use the question’s exact variant. This checks behavior on a small test batch—not performance on every possible input.
Python downloads only when you run code, using compressed runtime assets. Code is not saved or uploaded. Enable JavaScript to run it.
Printed output
Five-second execution limit per batch. Standard-library Python only; additional packages and network access are unavailable. Stop ends execution without blocking the lesson.
03. The idea
Try sketching your own approach first. What would you track, and why would it work?
Reveal the idea
- Emit value, left subtree, right subtree; emit null for absent nodes.
- Decode using one shared cursor.
- Export the rebuilt tree for comparison.
04. Watch it happen
Use Step to move slowly, or Play to follow the whole trace. Change a preset or load your own input.
Input & settings
Red = current item / blue = active window or cells / green = completed work. A value docks at its actual destination; the original input stays unchanged. Positions start at 0.
Working state / what changes
Ready to begin
Enable JavaScript to step through the animation. The worked example and solution below remain readable without it.
Python / why it changes
The line behind the step
class Node:
def __init__(self, value):
self.value, self.left, self.right = value, None, None
def tree(values, index=0):
if index >= len(values) or values[index] is None:
return None
node = Node(values[index])
node.left = tree(values, 2 * index + 1)
node.right = tree(values, 2 * index + 2)
return node
def export_tree(root):
slots = {}
def visit(node, index):
if node is None:
return
slots[index] = node.value
visit(node.left, 2 * index + 1)
visit(node.right, 2 * index + 2)
visit(root, 0)
return [slots.get(i) for i in range(max(slots, default=-1) + 1)]
def solve(data, parameter=""):
encoded = []
def encode(node):
if node is None:
encoded.append(None)
return
encoded.append(node.value)
encode(node.left)
encode(node.right)
encode(tree(data))
stream = iter(encoded)
def decode():
value = next(stream)
if value is None:
return None
node = Node(value)
node.left, node.right = decode(), decode()
return node
restored = decode()
return {"encoded": encoded, "decoded": export_tree(restored)}How to use this walkthrough
Hover or focus a control for its label. Play forms the input and follows values into the working state. Step shows one change; Back and the slider restore exact snapshots. Reduced motion uses instant updates. Saved snapshots and sorted heap displays are teaching overhead, not algorithm complexity.
05. Python solution
class Node:
def __init__(self, value):
self.value, self.left, self.right = value, None, None
def tree(values, index=0):
if index >= len(values) or values[index] is None:
return None
node = Node(values[index])
node.left = tree(values, 2 * index + 1)
node.right = tree(values, 2 * index + 2)
return node
def export_tree(root):
slots = {}
def visit(node, index):
if node is None:
return
slots[index] = node.value
visit(node.left, 2 * index + 1)
visit(node.right, 2 * index + 2)
visit(root, 0)
return [slots.get(i) for i in range(max(slots, default=-1) + 1)]
def solve(data, parameter=""):
encoded = []
def encode(node):
if node is None:
encoded.append(None)
return
encoded.append(node.value)
encode(node.left)
encode(node.right)
encode(tree(data))
stream = iter(encoded)
def decode():
value = next(stream)
if value is None:
return None
node = Node(value)
node.left, node.right = decode(), decode()
return node
restored = decode()
return {"encoded": encoded, "decoded": export_tree(restored)}06. Cost & edge cases
- Time
- O(n) plus slot output
- Space
- O(n)
- Validate the exact input format and bounds before tracing.
- Equal labels do not collapse vertex identity; missing nodes and invalid pointers are explicit.