Postorder Traversal

Return the postorder traversal of a binary tree as a list of node values.

binary-tree traversal recursion

Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder traversal visits nodes in the order: left subtree, right subtree, root.

Implement the function `postorder_traversal(root)` which takes the root node of a binary tree and returns a list of integers representing the postorder traversal.

Each node is defined as a class with attributes `val` (integer), `left` (Node or None), and `right` (Node or None). The tree is not necessarily binary search; it's a general binary tree. The number of nodes is at most 10^4.

You may use recursion or an iterative approach. Do not modify the tree.

Constraints

- The number of nodes in the tree is in the range [0, 10000].
- Node values are integers within [-1000, 1000].
- The function must return a list of integers in postorder.

Example

['>>> root = Node(1)\n>>> root.right = Node(2)\n>>> root.right.left = Node(3)\n>>> postorder_traversal(root)\n[3, 2, 1]', '>>> postorder_traversal(None)\n[]', '>>> root = Node(1)\n>>> postorder_traversal(root)\n[1]']

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

For each node, you need to traverse left, then right, then visit node.

If using recursion, think of the base case when root is None.

You can use a stack and a visited set or a two-stack method to avoid recursion.

Test Results

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