Abstract / Summary

Given the root of an n-ary tree return the postorder traversal of its nodes as a list

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 81% (500k+ submissions).

Typical patterns to solve this problem:

• Depth First Search
• Stack
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single public method postorder. This method performs a post-order traversal of an N-ary tree, returning the node values in the order in which each node is visited after all of its children. The traversal logic is encapsulated in a nested generator function named deeper. By yielding values directly from the generator, the implementation produces a lazy sequence rather than constructing an intermediate list.

Key Steps

The core of the algorithm resides in the nested deeper function:

def deeper(node):
    if node:
        for i in node.children:
            yield from deeper(i)
        yield node.val

The outer method simply invokes this generator with the root node:

return deeper(root)

The first step checks whether the current node reference is truthy. If the node is None, the function returns without yielding any value, effectively terminating that branch of recursion.

The second step iterates over the children collection of the current node. For each child i, the statement yield from deeper(i) delegates the iteration to the recursive call, streaming all values produced by the child’s subtree directly to the caller. This delegation eliminates the need for an explicit loop that would collect child results before yielding them.

The final step, yield node.val, emits the value of the current node after all of its descendants have been processed, satisfying the post-order requirement.

Edge Cases Handled

The recursive generator naturally accommodates several edge conditions:

• Empty tree - When root is None, the initial call to deeper receives a falsy argument. The guard if node: prevents any further execution, and the generator yields no elements. Consumers of the result simply receive an empty iterator.

• Leaf node - A node without children has an empty children iterable. The for loop executes zero times, and the generator proceeds directly to yield node.val, correctly emitting the leaf’s value as the sole element of its subtree.

• Highly unbalanced tree - The recursion depth follows the longest root-to-leaf path. Because the generator yields values incrementally, the call stack is the only additional memory consumption, and the algorithm remains correct regardless of how skewed the tree structure is.

• Nodes with many children - The for loop iterates over each child in order, and yield from streams each child’s subtree before moving to the next sibling. This preserves the left-to-right ordering expected in a typical post-order traversal of an N-ary tree.

Performance Optimizations

The implementation leverages Python’s generator protocol to achieve several performance benefits:

• Lazy evaluation - By yielding values as they are discovered, the algorithm avoids allocating a full list of node values. This reduces peak memory usage, especially for large trees where the number of nodes may be substantial.

• Direct delegation with yield from - The use of yield from passes control to the recursive generator without the overhead of manually iterating over its output and re-yielding each element. This results in a tighter execution path and fewer Python bytecode instructions per yielded value.

• Minimal data copying - Since each node’s value is emitted exactly once and never stored in an intermediate container, the code eliminates unnecessary copying of integers or references, contributing to faster overall traversal when the consumer processes values on the fly.

Collectively, these choices make the traversal both memory-efficient and streamlined in terms of execution flow, while preserving the clarity of a straightforward recursive definition.

Imagine you are holding a big, beautiful tree made of wooden blocks. This specific tree has a special rule for playing. You have a little helper character that starts at the very top of the tree, which is called the root.

The helper looks at where it is standing and notices that each block can have several smaller blocks hanging underneath it like branches. The helper goes down into those branches one by one to see what is hidden deep inside. It keeps going down as far as it can until it reaches the very last block at the bottom of a branch.

Once the helper reaches a block that has no more branches underneath it, it says the number written on that block out loud. After saying the number, the helper climbs back up to the block right above it to check if there are any other branches it missed. It repeats this over and over again, visiting every single branch and every single block. The helper always makes sure to look at all the little branches first before it ever says the number written on the big block it is currently holding onto. By the time the helper finishes visiting every spot, all the numbers have been called out in a special order starting from the bottom of the tree and working all the way back up to the top.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java					Go	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem						Ruby
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	Shamik07							Dart
	sonugiri1043	C++
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
Shamik07	Dart
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality