AST Visitor Lite

Traverse a simplified abstract syntax tree and collect the names of all identifiers.

trees traversal ast

You are given a simplified abstract syntax tree (AST) represented as a Python dictionary with the following node types:
- `{"type": "Identifier", "name": "x"}`
- `{"type": "Literal", "value": 42}`
- Binary expression: `{"type": "BinaryExpression", "left": <node>, "right": <node>}`
- Call expression: `{"type": "CallExpression", "callee": <node>, "arguments": [<node>, ...]}`
- Variable declaration: `{"type": "VariableDeclaration", "declarations": [{"type": "VariableDeclarator", "id": <node>, "init": <node>}]}`

Implement the function `collect_identifiers(node)` that takes an AST root node (as a dict) and returns a list of names of all `Identifier` nodes in **pre-order traversal** (the order they appear in the source code, i.e., left-to-right, top-to-bottom). Other node types contribute nothing but their children are still traversed in the natural order: for `BinaryExpression` traverse `left` then `right`; for `CallExpression` traverse `callee` then each argument in order; for `VariableDeclaration` traverse each declarator in order, and within a declarator traverse `id` then `init`.

Return the list of names in the order encountered. The input is guaranteed to be a valid AST according to the above structure. The depth of the tree is at most 1000.

Constraints

The AST is a dictionary conforming to the described node types. The total number of nodes is at most 10^4. The depth is at most 1000. The names are non-empty strings. You may assume no cycles.

Example

>>> collect_identifiers({'type': 'Identifier', 'name': 'x'})
['x']
>>> ast = {'type': 'BinaryExpression', 'left': {'type': 'Identifier', 'name': 'a'}, 'right': {'type': 'Literal', 'value': 5}}
>>> collect_identifiers(ast)
['a']
>>> ast = {'type': 'CallExpression', 'callee': {'type': 'Identifier', 'name': 'foo'}, 'arguments': [{'type': 'Identifier', 'name': 'bar'}, {'type': 'Literal', 'value': 1}]}
>>> collect_identifiers(ast)
['foo', 'bar']

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Write a recursive function that checks the node's type and recurses on children.

For a VariableDeclarator, append the id's name when recursing into id; init is just a node.

For node types like Literal, you don't need to recurse.

The order of traversal is: as soon as you see an Identifier, add its name; then recurse into children in the order specified.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.