Parse and Reconstruct Stack Trace
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given a multi-line stack trace string from a single thread (e.g., each frame is in the form 'at Module::Function(file:line)'), design and implement a parser that:
(
1) extracts the ordered list of frames from most recent to oldest;
(
2) reconstructs the call hierarchy as a tree; and
(
3) identifies the deepest frame associated with the thrown exception. The parser must correctly handle nested causes (e.g., 'Caused by:' sections), abbreviated repeated frames (e.g., '... N more'), and missing or malformed lines. Describe your data structures, time/space complexity, and provide working code for parse and reconstruction.
Quick Answer: This question evaluates parsing and string-processing skills, hierarchical data structure design for call-tree reconstruction, exception trace analysis, and algorithmic complexity reasoning for robust log handling.
Part 1: Extract Frames from the Outermost Stack Trace Section
Extract the valid stack-frame lines from the **outermost (first) exception section** of a multi-line stack trace.
## Function
```python
def solution(trace):
...
```
- **Input:** `trace` — a single string containing the whole stack trace, with lines separated by newlines. It may be empty.
- **Output:** a **list of strings**, one per valid frame, in the same order they appear in the input (**most recent call first, oldest call last**).
## Line format
Read the trace line by line. Before testing a line, **trim leading/trailing whitespace**.
A line is a **valid frame** if, after trimming, it has the form:
```
at Module::Function(file:line)
```
Concretely, a trimmed line qualifies only when **all** of the following hold:
- It starts with the prefix `at ` (the word `at` followed by a space).
- Let **body** be the text after that prefix, with its own surrounding whitespace trimmed (e.g. `Module::Function(file:line)`).
- **body** ends with a closing parenthesis `)`.
- **body** contains an opening parenthesis `(` and, after it, a colon `:` (use the **last** `(` and the **last** `:`); the `(` must come before the `:`, and the `:` must not be the final character (so a line number follows it).
- The text between that `:` and the closing `)` is the **line number**: it must be **non-empty and consist only of digits** (a non-negative integer).
- The text before the `(` (the `Module::Function` part) must be **non-empty**.
## What to return for each frame
For a valid frame, append the **body** — that is, the frame **without** the leading `at ` prefix and with surrounding whitespace removed (e.g. `App::run(app.py:10)`). Do not include `at ` in the output.
## Section boundary
Scan the lines top to bottom. As soon as you reach a line whose **trimmed** form starts with `Caused by:`, **stop immediately** — that line and everything after it belongs to a nested cause and must be ignored. Only the first (outermost) exception section is parsed.
## Other rules
- **Skip** any line that is blank, malformed, or does not match the valid-frame format (e.g. header lines like `RuntimeError: boom` or `random text`, or a frame whose body has no `(...:...)` shape such as `at BadLine(nope)`).
- If `trace` is empty, or if a `Caused by:` line appears before any valid frame, return an **empty list**.
- Preserve the original order of the valid frames you keep (most recent to oldest).
## Constraints
- `0 <= len(trace) <= 200000`
- The trace contains at most `10000` lines.
- A valid frame line must start with `at ` after trimming and must end with `(file:line)`, where `line` is a non-negative integer.
- Only the first exception section is parsed; later `Caused by:` sections are ignored.
## Examples
**Input**
```
RuntimeError: boom
at App::run(app.py:10)
at Main::main(main.py:20)
```
**Output:** `['App::run(app.py:10)', 'Main::main(main.py:20)']`
---
**Input**
```
ValueError
random text
at Parser::parse(parser.py:7)
at BadLine(nope)
Caused by: IOError
at IO::read(io.py:3)
```
**Output:** `['Parser::parse(parser.py:7)']`
(`ValueError` and `random text` are not frames; `at BadLine(nope)` has no `:` after its `(`, so it fails the `(file:line)` format; parsing stops at `Caused by:`, so `at IO::read(io.py:3)` is ignored.)
---
**Input**
```
TopError
Caused by: Inner
at X::f(x.py:1)
```
**Output:** `[]` (the `Caused by:` line ends the section before any frame is collected.)
Constraints
- 0 <= len(trace) <= 200000
- The trace contains at most 10000 lines.
- A valid frame line must start with 'at ' after trimming and must end with '(file:line)' where line is a non-negative integer.
- Only the first exception section should be parsed; later 'Caused by:' sections are ignored.
Examples
Input: 'RuntimeError: boom\nat App::run(app.py:10)\nat Main::main(main.py:20)'
Expected Output: ['App::run(app.py:10)', 'Main::main(main.py:20)']
Explanation: Both frame lines are valid and belong to the outermost section.
Input: 'ValueError\nrandom text\n at Parser::parse(parser.py:7)\nat BadLine(nope)\nCaused by: IOError\nat IO::read(io.py:3)'
Expected Output: ['Parser::parse(parser.py:7)']
Explanation: The malformed line is skipped, and parsing stops before the cause section.
Input: ''
Expected Output: []
Explanation: Empty input has no frames.
Input: 'TopError\nCaused by: Inner\nat X::f(x.py:1)'
Expected Output: []
Explanation: There are no outermost frames before the first cause section.
Input: 'Oops\n at One::only(one.py:1) '
Expected Output: ['One::only(one.py:1)']
Explanation: Leading and trailing spaces should be ignored when validating a frame line.
Solution
def solution(trace):
def parse_frame(line):
stripped = line.strip()
if not stripped.startswith('at '):
return None
body = stripped[3:].strip()
if not body.endswith(')'):
return None
open_paren = body.rfind('(')
colon = body.rfind(':')
if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1:
return None
line_no = body[colon + 1:-1]
if not line_no.isdigit() or not body[:open_paren]:
return None
return body
if not trace:
return []
frames = []
for line in trace.splitlines():
if line.strip().startswith('Caused by:'):
break
frame = parse_frame(line)
if frame is not None:
frames.append(frame)
return framesExplanation
**Approach.** We do a single linear scan over the lines of `trace`, stopping at the boundary of the outermost exception section, and keep only the lines that look like valid frames.
**Section boundary.** We split with `trace.splitlines()` and walk the lines top-to-bottom (already most-recent-to-oldest). The moment a line's `strip()`ped form `startswith('Caused by:')`, we `break` — everything from there on belongs to a nested cause and is ignored. An empty `trace` short-circuits to `[]` up front.
**Frame validation (`parse_frame`).** For each surviving line we trim whitespace and require:
- it starts with `'at '`; we then take `body = stripped[3:].strip()` (the frame without the `at ` prefix);
- `body` ends with `')'`;
- using `rfind('(')` and `rfind(':')`, the last `(` and last `:` exist with `'('` before `':'`, and the `:` is not the final character (so a line number follows);
- the substring after `:` up to the closing `)` (`body[colon+1:-1]`) is all digits (`isdigit()`), i.e. a non-negative integer line number;
- the part before `(` (`body[:open_paren]`, the `Module::Function`) is non-empty.
Lines failing any check return `None` and are skipped; valid ones append `body` (e.g. `App::run(app.py:10)`).
**Why it's correct.** Order is preserved because we append in iteration order and never reorder. Blank/malformed/unrelated lines simply fail validation. Using `rfind` for `(` and `:` tolerates these characters appearing earlier in the module/function name while still anchoring on the trailing `(file:line)`. The `break` guarantees only the first section is parsed.
Time complexity: O(n), where n is the total number of characters in the trace. Each line is scanned a constant number of times (strip, rfind, slice), so the work is linear in the input size.. Space complexity: O(n) in the worst case. splitlines() materializes the lines and the output list can hold up to O(n) characters of frame data; auxiliary work per line is O(1)..
Hints
- Process the trace line by line and stop at the first 'Caused by:' line.
- You do not need a full parser; checking the position of '(', ':', and ')' is enough to validate a frame.
Part 2: Reconstruct a Merged Call Hierarchy Tree
Reconstruct the merged call hierarchy of a single thread's stack trace and return it as a **forest of nested dictionaries**.
## Function
```python
def solution(trace):
...
```
`trace` is a single string containing the full multi-line stack trace (lines separated by `\n`). Return a nested dictionary of the form `{frame: child_subtree}` (see **Output** below).
## Background
A stack trace may contain several **exception sections** chained by `Caused by:` lines, and a section may abbreviate its repeated tail using a `... N more` line. Your job is to rebuild every section's full call stack and merge them all into one tree.
## Frame lines
After trimming surrounding whitespace, a **valid frame line** has the form:
```
at Module::Function(file:line)
```
A line is a valid frame **only if** the trimmed line:
- starts with `at ` (the literal `at` followed by a space), and
- ends with `)`, and
- contains an opening `(` that comes before the final `:`, and
- has a non-empty part before that `(`, and
- has a **line number** (the text between the final `:` and the closing `)`) consisting only of digits (a non-negative integer).
The **frame** you record is the part of the line **after** `at ` (for example, the line `at B::b(b.py:2)` yields the frame `B::b(b.py:2)`). Lines that do not satisfy every rule above are **malformed** and must be ignored.
## Sections
- The **first section** begins at the start of the trace.
- Each line whose trimmed form starts with `Caused by:` ends the current section and begins a **new section** (the `Caused by:` line itself is not a frame).
- Within a section, valid frame lines are collected **in the order they appear**, which is most recent call first down to oldest call.
## The `... N more` abbreviation
A line whose trimmed form starts with `... ` and ends with ` more`, with a digit-only number `N` in between, is an **abbreviation line**. Each section contains **at most one** such line.
When a section (other than the first) has an abbreviation `... N more`, append the **last N frames of the previous section's fully reconstructed stack** to this section's collected frames:
- "Previous" means the section immediately before this one, **after** that section has itself been fully reconstructed (so abbreviations chain transitively through `Caused by:` sections).
- If `N` is larger than the number of frames in the previous reconstructed stack, append **all** of them.
- An abbreviation line in the first section (which has no previous section) contributes nothing.
## Output
Insert every fully reconstructed stack into a single tree, walking each stack from its **oldest call to its most recent call**. The tree is represented by nested dictionaries: each frame maps to the dictionary of its child frames, e.g. `{frame: {childFrame: {...}}}`. A leaf frame maps to an empty dictionary `{}`.
- Stacks that share a common prefix of oldest calls share those nodes in the tree.
- If multiple disconnected roots exist, they all appear at the **top level** of the returned dictionary.
- An empty reconstructed stack (for example, a section with only malformed lines) contributes nothing.
## Edge cases
- An empty `trace` returns `{}`.
- Malformed lines, blank lines, and exception-description lines are silently skipped.
## Example
Input:
```
Outer
at Service::run(s.py:30)
at Controller::handle(c.py:20)
at Main::main(m.py:10)
Caused by: ParseError
at Parser::parse(p.py:5)
... 2 more
```
The first section's stack (most recent → oldest) is `Service::run`, `Controller::handle`, `Main::main`. The second section starts with `Parser::parse`, then `... 2 more` appends the last 2 frames of the previous reconstructed stack (`Controller::handle`, `Main::main`), giving `Parser::parse`, `Controller::handle`, `Main::main`. Inserting both stacks oldest-first and merging the shared `Main::main → Controller::handle` prefix produces:
```python
{"Main::main(m.py:10)": {"Controller::handle(c.py:20)": {"Service::run(s.py:30)": {}, "Parser::parse(p.py:5)": {}}}}
```
## Constraints
- `0 <= len(trace) <= 200000`
- The trace contains at most 10000 lines.
- Each section contains at most one abbreviation line of the form `... N more`.
- A valid frame line must start with `at ` after trimming and must end with `(file:line)` where `line` is a non-negative integer.
Constraints
- 0 <= len(trace) <= 200000
- The trace contains at most 10000 lines.
- Each section contains at most one abbreviation line of the form '... N more'.
- A valid frame line must start with 'at ' after trimming and must end with '(file:line)' where line is a non-negative integer.
Examples
Input: 'Err\nat B::b(b.py:2)\nat A::a(a.py:1)'
Expected Output: {'A::a(a.py:1)': {'B::b(b.py:2)': {}}}
Explanation: A single stack becomes a single root-to-leaf path from oldest to newest.
Input: 'Outer\nat Service::run(s.py:30)\nat Controller::handle(c.py:20)\nat Main::main(m.py:10)\nCaused by: ParseError\nat Parser::parse(p.py:5)\n... 2 more'
Expected Output: {'Main::main(m.py:10)': {'Controller::handle(c.py:20)': {'Service::run(s.py:30)': {}, 'Parser::parse(p.py:5)': {}}}}
Explanation: The cause expands to [Parser::parse, Controller::handle, Main::main], creating a branch under Controller::handle.
Input: 'Top\nat A1::f(a1.py:4)\nat Root::main(root.py:1)\nCaused by: Mid\nat B1::g(b1.py:3)\n... 1 more\nCaused by: Low\nat C1::h(c1.py:2)\n... 2 more'
Expected Output: {'Root::main(root.py:1)': {'A1::f(a1.py:4)': {}, 'B1::g(b1.py:3)': {'C1::h(c1.py:2)': {}}}}
Explanation: Each deeper cause is expanded from the previous section, producing a shared prefix and a longer branch.
Input: ''
Expected Output: {}
Explanation: An empty trace has no hierarchy.
Input: 'E\nnoise\nat X::x(x.py:2)\nat Main::main(main.py:1)\nCaused by: Y\nbad\n... 5 more'
Expected Output: {'Main::main(main.py:1)': {'X::x(x.py:2)': {}}}
Explanation: The malformed line is ignored, and the oversized abbreviation copies only the available parent suffix.
Solution
def solution(trace):
def parse_frame(line):
stripped = line.strip()
if not stripped.startswith('at '):
return None
body = stripped[3:].strip()
if not body.endswith(')'):
return None
open_paren = body.rfind('(')
colon = body.rfind(':')
if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1:
return None
line_no = body[colon + 1:-1]
if not line_no.isdigit() or not body[:open_paren]:
return None
return body
def parse_more(line):
stripped = line.strip()
if not stripped.startswith('... ') or not stripped.endswith(' more'):
return None
middle = stripped[4:-5].strip()
if not middle.isdigit():
return None
return int(middle)
if not trace:
return {}
sections = []
current = {'frames': [], 'omitted': 0}
for line in trace.splitlines():
if line.strip().startswith('Caused by:'):
sections.append(current)
current = {'frames': [], 'omitted': 0}
continue
frame = parse_frame(line)
if frame is not None:
current['frames'].append(frame)
continue
omitted = parse_more(line)
if omitted is not None:
current['omitted'] = omitted
sections.append(current)
full_sections = []
for i, section in enumerate(sections):
frames = list(section['frames'])
omitted = section['omitted']
if omitted > 0 and i > 0:
parent = full_sections[i - 1]
k = min(omitted, len(parent))
if k > 0:
frames.extend(parent[-k:])
full_sections.append(frames)
forest = {}
for frames in full_sections:
if not frames:
continue
node = forest
for frame in reversed(frames):
if frame not in node:
node[frame] = {}
node = node[frame]
return forestExplanation
The solution reconstructs each exception section's stack independently, resolving `... N more` abbreviations against the **previous reconstructed** stack, then merges all stacks into a nested-dict forest.
**Parsing helpers.**
- `parse_frame` validates a line of the shape `at Module::Function(file:line)`: after trimming it must start with `at `, end with `)`, contain a last `(` before a last `:`, have a purely-numeric line number, and a non-empty prefix before `(`. It returns the body (everything after `at `), or `None` for malformed lines.
- `parse_more` recognizes `... N more` and returns `N`.
**Splitting into sections.** Iterating `trace.splitlines()`, a `Caused by:` line closes the current section and opens a new one. Within a section, frames are collected **in appearance order** (most-recent → oldest), and the section's single `omitted` count is recorded. Non-frame, non-`more` lines (like `noise`/`bad`) are silently ignored.
**Reconstructing.** For section `i`, if `omitted > 0` and `i > 0`, it appends the last `k = min(omitted, len(prev))` frames of `full_sections[i-1]` — the *already-reconstructed* prior stack, not its raw frames. This is why chained `Caused by:` sections inherit transitively (test 3). Clamping to `len(prev)` handles `N` larger than available frames.
**Building the forest.** Each reconstructed stack is inserted from **oldest to most-recent** by iterating `reversed(frames)`, creating child dicts as needed (`{frame: child_subtree}`). Shared call prefixes merge naturally, and disconnected roots coexist at the top level. Empty stacks are skipped, so an all-malformed section contributes nothing (test 5).
Time complexity: O(n + T), where n is the total number of characters in the trace (scanning/splitting every line once) and T is the total number of frames across all reconstructed stacks (each frame is appended during reconstruction and inserted once into the tree). Tree insertion is O(1) average per frame via dict lookups.. Space complexity: O(T), for storing the reconstructed stacks (each frame string referenced) plus the merged forest, whose total node count is bounded by the number of inserted frames..
Hints
- First reconstruct each section's full frame list; only then build the hierarchy.
- A trie built from oldest to most recent frames naturally merges shared call prefixes.
Part 3: Find the Deepest Frame of the Thrown Exception
# Find the Deepest Frame of the Thrown Exception
Given a Java-style stack trace as a single string `trace`, return the **deepest frame of the actually-thrown exception**, or `None` if no such frame can be recovered.
Implement:
```python
def solution(trace):
...
```
## Background
A stack trace is divided into **sections**. The first section is the original error; each subsequent section is introduced by a line whose trimmed text begins with `Caused by:`. These sections form a *cause chain*, and the **last section in the chain is the actually-thrown exception** — the one whose deepest frame you must report.
Within a section, frames are listed **most-recent first** (top) to **oldest last** (bottom). The call hierarchy is rooted at the oldest call, so the **deepest frame is the most-recent frame** — i.e. the **first** valid frame listed in the last section after expansion.
## Line types
Parse the trace **line by line** (split on newlines). Each line, after trimming surrounding whitespace, is one of:
- **Section header** — starts with `Caused by:`. Closes the current section and begins a new one.
- **Frame line** — a valid frame has the trimmed form `at Module::Function(file:line)`. Specifically, after trimming it must:
- start with `at ` (then take the remaining text as the **frame body**, e.g. `Module::Function(file:line)`),
- end with `)`,
- contain a `(` such that the text before the last `(` is **non-empty**, and
- have, between the last `(` and the closing `)`, a `file:line` part whose portion **after the last `:` is a non-negative integer** (all digits).
The value you ultimately return is this **frame body** (the text after `at `), e.g. `B::work(b.py:2)`.
- **Abbreviation line** — the form `... N more` (trimmed text starts with `... ` and ends with ` more`, with `N` a non-negative integer in between). It means: this section's stack continues with the **last `N` frames of the previous section's fully reconstructed stack**. Each section contains **at most one** abbreviation line.
- **Anything else** (including the leading exception-message line of a section, and any malformed frame) is **ignored**.
## Reconstruction
Process sections in order. For each section, its reconstructed frame list is its own explicit valid frames followed by, **if it has a `... N more` and a previous section exists**, the last `k = min(N, len(previous_reconstructed))` frames of the **previous *fully reconstructed*** section (so inheritance composes across multiple nested causes). Inherited frames are appended **after** the section's own frames.
## Return value
Return the **first frame** (index `0`, the most-recent / deepest) of the **last** section's reconstructed frame list.
Return `None` when:
- the trace is empty, or
- the last section has **no** recoverable frame (no valid explicit frame and nothing recovered via `... N more`).
Note: if the deepest section has no explicit valid frames, you may still recover its frames purely from `... N more`.
## Constraints
- `0 <= len(trace) <= 200000`
- The trace contains at most `10000` lines.
- Each section contains at most one abbreviation line of the form `... N more`.
- A valid frame line must start with `at ` after trimming and must end with `(file:line)` where `line` is a non-negative integer.
## Examples
**Example 1**
```
Error
at B::work(b.py:2)
at A::main(a.py:1)
```
Single section; first valid frame is the deepest. Returns `B::work(b.py:2)`.
**Example 2**
```
Outer
at Service::run(s.py:3)
at Main::main(m.py:1)
Caused by: Inner
at Parser::parse(p.py:2)
... 1 more
```
The last (thrown) section's first frame is `Parser::parse(p.py:2)`. Returns `Parser::parse(p.py:2)`.
**Example 3**
```
Outer
at X::x(x.py:2)
at Main::main(m.py:1)
Caused by: Inner
bad line
... 2 more
```
The last section has no valid explicit frame; its frames are recovered from `... 2 more` (the last 2 frames of the reconstructed parent). The deepest is `X::x(x.py:2)`. Returns `X::x(x.py:2)`.
**Example 4**
```
(empty string)
```
Returns `None`.
Constraints
- 0 <= len(trace) <= 200000
- The trace contains at most 10000 lines.
- Each section contains at most one abbreviation line of the form '... N more'.
- A valid frame line must start with 'at ' after trimming and must end with '(file:line)' where line is a non-negative integer.
Examples
Input: 'Error\nat B::work(b.py:2)\nat A::main(a.py:1)'
Expected Output: 'B::work(b.py:2)'
Explanation: With no nested cause, the thrown exception is the outermost section, and its deepest node is the most recent frame.
Input: 'Outer\nat Service::run(s.py:3)\nat Main::main(m.py:1)\nCaused by: Inner\nat Parser::parse(p.py:2)\n... 1 more'
Expected Output: 'Parser::parse(p.py:2)'
Explanation: The deepest cause expands to [Parser::parse, Main::main], so the deepest node is Parser::parse.
Input: 'Top\nat A::a(a.py:4)\nat Root::main(root.py:1)\nCaused by: Mid\nat B::b(b.py:3)\n... 1 more\nCaused by: Low\nat C::c(c.py:2)\n... 2 more'
Expected Output: 'C::c(c.py:2)'
Explanation: The final cause section reconstructs to [C::c, B::b, Root::main], and the deepest node is C::c.
Input: ''
Expected Output: None
Explanation: Empty input cannot produce a frame.
Input: 'Outer\nat X::x(x.py:2)\nat Main::main(m.py:1)\nCaused by: Inner\nbad line\n... 2 more'
Expected Output: 'X::x(x.py:2)'
Explanation: The deepest cause has no valid explicit frame, but expansion recovers [X::x, Main::main].
Solution
def solution(trace):
def parse_frame(line):
stripped = line.strip()
if not stripped.startswith('at '):
return None
body = stripped[3:].strip()
if not body.endswith(')'):
return None
open_paren = body.rfind('(')
colon = body.rfind(':')
if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1:
return None
line_no = body[colon + 1:-1]
if not line_no.isdigit() or not body[:open_paren]:
return None
return body
def parse_more(line):
stripped = line.strip()
if not stripped.startswith('... ') or not stripped.endswith(' more'):
return None
middle = stripped[4:-5].strip()
if not middle.isdigit():
return None
return int(middle)
if not trace:
return None
sections = []
current = {'frames': [], 'omitted': 0}
for line in trace.splitlines():
if line.strip().startswith('Caused by:'):
sections.append(current)
current = {'frames': [], 'omitted': 0}
continue
frame = parse_frame(line)
if frame is not None:
current['frames'].append(frame)
continue
omitted = parse_more(line)
if omitted is not None:
current['omitted'] = omitted
sections.append(current)
full_sections = []
for i, section in enumerate(sections):
frames = list(section['frames'])
omitted = section['omitted']
if omitted > 0 and i > 0:
parent = full_sections[i - 1]
k = min(omitted, len(parent))
if k > 0:
frames.extend(parent[-k:])
full_sections.append(frames)
deepest_section = full_sections[-1] if full_sections else []
if not deepest_section:
return None
return deepest_section[0]Explanation
**Approach.** A stack trace is split into *sections* by `Caused by:` lines; the last section is the actually-thrown exception. We want its **deepest frame**, defined here as the *most recent* frame (index `0`) of the last section after expanding any `... N more` abbreviation.
**Parsing.** Two helpers validate lines:
- `parse_frame` accepts a line that, trimmed, starts with `at ` and ends with `(file:line)` where `line` is all digits, and the part before `(` is non-empty. It returns the canonical `Module::Function(file:line)` body; anything malformed returns `None` and is ignored.
- `parse_more` reads `... N more`, returning the integer `N`.
We sweep every line once. A `Caused by:` flushes the `current` section and starts a fresh one. Otherwise we try to parse a frame (appended to `current['frames']`) or a `... N more` (stored as `current['omitted']`, at most one per section). After the loop the final `current` is appended.
**Reconstruction.** Sections are processed in order. For section `i`, if it has `omitted > 0` and a previous section exists, we take the **last `k = min(omitted, len(parent))` frames of the previous *fully reconstructed* section** (`full_sections[i-1]`, not its raw frames) and append them. This is correct because `... N more` means "the remaining frames are identical to the tail of the enclosing stack," and chaining off the already-expanded parent makes the rule compose across multiple nested causes.
**Result.** The deepest path is the last reconstructed section; we return its element `0` (most recent frame), or `None` when the trace is empty or that section has no recoverable frame. Test 5 shows recovery purely from `... N more` when explicit frames are malformed.
Time complexity: O(n + T), where n is the number of characters in the trace (one `splitlines` pass plus constant work per line) and T is the total number of frames across all reconstructed sections (each `... N more` can copy up to the parent's full length).. Space complexity: O(T) for the per-section frame lists and the reconstructed `full_sections` (which may duplicate inherited tail frames); bounded by the total reconstructed frame count..
Hints
- The thrown exception is the last section, not the first one.
- To expand '... N more', reuse the suffix of the previous section's reconstructed frame list.