Binary Tree Postorder Traversal

Binary Tree Postorder Traversal is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [3,2,1]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,6,7,5,2,9,8,3,1]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

- The number of the nodes in the tree is in the range [0, 100].

- -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Topics and companies

Topics: Stack, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Amazon.

How to practise Binary Tree Postorder Traversal on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Binary Tree Postorder Traversal in the code editor, or read the Binary Tree Postorder Traversal editorial for a worked solution with its approach and complexity analysis.

Where Binary Tree Postorder Traversal sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Postorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Binary Tree Postorder Traversal

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• All Nodes Distance K in Binary Tree — Medium, same subpattern
• Balanced Binary Tree — Easy, same subpattern
• Binary Tree Maximum Path Sum — Hard, same subpattern
• Delete Nodes And Return Forest — Medium, same subpattern
• Diameter of Binary Tree — Easy, same subpattern
• Find Leaves of Binary Tree — Medium, same subpattern