Binary tree traversals
Problem Introduction
In this problem you will implement in-order, pre-order and post-order traversals of a binary tree. These
traversals were defined in the week 1 lecture on tree traversals, but it is very useful to practice implementing
them to understand binary search trees better.
Problem Description
Task. You are given a rooted binary tree. Build and output its in-order, pre-order and post-order traversals.
Input Format. The first line contains the number of vertices 𝑛. The vertices of the tree are numbered
from 0 to 𝑛 − 1. Vertex 0 is the root.
The next 𝑛 lines contain information about vertices 0, 1, ..., 𝑛−1 in order. Each of these lines contains
three integers 𝑘𝑒𝑦𝑖
, 𝑙𝑒𝑓 𝑡𝑖 and 𝑟𝑖𝑔𝑡𝑖 — 𝑘𝑒𝑦𝑖
is the key of the 𝑖-th vertex, 𝑙𝑒𝑓 𝑡𝑖
is the index of the left
child of the 𝑖-th vertex, and 𝑟𝑖𝑔𝑡𝑖
is the index of the right child of the 𝑖-th vertex. If 𝑖 doesn’t have
left or right child (or both), the corresponding 𝑙𝑒𝑓 𝑡𝑖 or 𝑟𝑖𝑔𝑡𝑖 (or both) will be equal to −1.
Constraints. 1 ≤ 𝑛 ≤ 105
; 0 ≤ 𝑘𝑒𝑦𝑖 ≤ 109
; −1 ≤ 𝑙𝑒𝑓 𝑡𝑖
, 𝑟𝑖𝑔𝑡𝑖 ≤ 𝑛 − 1. It is guaranteed that the input
represents a valid binary tree. In particular, if 𝑙𝑒𝑓 𝑡𝑖 ̸= −1 and 𝑟𝑖𝑔𝑡𝑖 ̸= −1, then 𝑙𝑒𝑓 𝑡𝑖 ̸= 𝑟𝑖𝑔𝑡𝑖
. Also,
a vertex cannot be a child of two different vertices. Also, each vertex is a descendant of the root vertex.
Output Format. Print three lines. The first line should contain the keys of the vertices in the in-order
traversal of the tree. The second line should contain the keys of the vertices in the pre-order traversal
of the tree. The third line should contain the keys of the vertices in the post-order traversal of the tree.
Time Limits.
language C C++ Java Python C# Haskell JavaScript Ruby Scala
time (sec) 1 1 12 6 1.5 2 6 6 12
Memory Limit. 512MB.
Sample 1.
Input:
5
4 1 2
2 3 4
5 -1 -1
1 -1 -1
3 -1 -1
Output:
1 2 3 4 5
4 2 1 3 5
1 3 2 5 4
Solution :
#26|2|2021
#Edit
import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
class TO:
def read(self):
self.n = int(sys.stdin.readline())
self.key = [0 for _ in range(self.n)]
self.left = [0 for _ in range(self.n)]
self.right = [0 for _ in range(self.n)]
for i in range(self.n):
self.key[i], self.left[i], self.right[i] = map(
int, sys.stdin.readline().split()
)
def in_order(self):
current_id = 0
stack = []
while True:
if current_id != -1:
stack.append(current_id)
current_id = self.left[current_id]
elif stack:
current_id = stack.pop()
yield self.key[current_id]
current_id = self.right[current_id]
else:
break
def pre_order(self):
current_id = 0
stack = []
while True:
if current_id != -1:
yield self.key[current_id]
stack.append(current_id)
current_id = self.left[current_id]
elif stack:
current_id = stack.pop()
current_id = self.right[current_id]
else:
break
def post_order(self):
stack1 = [0]
stack2 = []
while stack1:
current_id = stack1.pop()
stack2.append(self.key[current_id])
left_id = self.left[current_id]
right_id = self.right[current_id]
if left_id != -1:
stack1.append(left_id)
if right_id != -1:
stack1.append(right_id)
while stack2:
yield stack2.pop()
def main():
tree = TO()
tree.read()
print(" ".join(str(x) for x in tree.in_order()))
print(" ".join(str(x) for x in tree.pre_order()))
print(" ".join(str(x) for x in tree.post_order()))
threading.Thread(target=main).start()