Binary Tree — Preorder Traversal
Practice this coding question on Coding Gurukul.
Problem statement
Given a binary tree, print its preorder traversal. Visit nodes in this order: node, left subtree, right subtree. 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 0 1 3 4 2.
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
0 1 3 4 2
Sign in to run or submit a solution in C++, Java or Python.