Mock 3 — Trees (60 min)

Download and complete the starter notebook

Use the Download starter notebook button on this lesson. Open the .ipynb in JupyterLab, Jupyter Notebook, or another compatible Python 3 environment. Work in a saved copy, complete the TODOs and reflection cells, run the public checks, add the requested tests, then upload that completed .ipynb to this lesson. Do not submit a blank starter. The notebook intentionally contains no answer key or private reviewer rubric.

Instructions

You have 60 minutes. Use this node contract:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

For LCA, p and q are guaranteed to be distinct node objects present in the tree. Values may repeat; identify targets by object identity. For codec, assume valid serialized input generated by your serializer; explain how malformed input would be rejected. Empty-tree serialization must be defined.

Problem 1 — Maximum Depth (Easy, about 10 minutes)

Implement max_depth(root), returning the number of nodes on the longest root-to-leaf path. An empty tree has depth 0.

Problem 2 — Lowest Common Ancestor (Medium, about 15 minutes)

Implement lowest_common_ancestor(root, p, q) for a general binary tree, not necessarily a BST. Return the lowest node that has both targets among its descendants (a node counts as its own descendant).

Problem 3 — Diameter of a Binary Tree (Medium, about 15 minutes)

Implement diameter_of_binary_tree(root). Return the number of edges on the longest path between any two nodes. Empty and single-node trees have diameter 0.

Problem 4 — Serialize and Deserialize (Hard, about 20 minutes)

Implement Codec.serialize(root) and Codec.deserialize(data) so deserializing a serialized tree reconstructs the same values and shape. Values are integers and may repeat. Choose and document an unambiguous format with explicit null markers. Encode the empty tree explicitly.

Submit the completed notebook

• Download this lesson's starter Jupyter notebook, complete the requested functions, and upload the saved .ipynb file here.
• Keep your implementation, added tests, complexity reasoning, and interview reflection in the notebook. No separate source file or NOTES.md is required.
• Do not upload the untouched starter. Public checks are examples, not a complete test suite; add the edge cases requested in the notebook.
• The downloadable notebook contains no reference solutions or reviewer rubric. Notebook outputs are not used as proof of correctness; the reviewer checks your submitted source and written reasoning.