Binary Tree — Postorder Traversal

Practice this coding question on Coding Gurukul.

Problem statement

Given a binary tree, print its postorder traversal. Visit nodes in this order: left subtree, right subtree, node. Nodes are numbered 0 to n-1. Node 0 is the root. Each input row gives that node’s left and right child IDs; -1 means no child. The input describes a valid tree containing all n nodes. Print each node ID once. If n=0, print EMPTY. Use an explicit stack and O(n) time. Worked example Node 0 has children 1 and 2. Node 1 has children 3 and 4. The traversal is 3 4 1 2 0.

Input format

First line: n. Next n lines: left right for node 0, node 1, and so on.

Output format

Print the traversal IDs separated by spaces, or EMPTY.

Constraints

0 <= n <= 100000; each child is -1 or an ID in [0,n-1]. Input is a valid rooted binary tree.

Sample input

5
1 2
3 4
-1 -1
-1 -1
-1 -1

Sample output

3 4 1 2 0

Sign in to run or submit a solution in C++, Java or Python.