Another Tree Problem

All submissions for this problem are available.
A binary search tree is a tree in which every node can have at most two child nodes. Considering any node $R$ with key $K$, nodes having key smaller than $K$ are in the left subtree rooted at $R$ whereas nodes having key larger than $K$ are in the right subtree rooted at $R$. Chef is fascinated by BSTs. Given an ordinary binary tree, he wonders what would be the inorder traversal of it were it converted to a binary search tree. You are given $M$ lines describing an ordinary binary tree. Each of the $M$ lines, contain 3 space separated integers, $X,\ U\ and\ V$ denoting the keys of a node, and itâ€™s left and right child. Remember, if no children are specified for a node, then it is assumed to have no children. Also, $1$ denotes that no child is present e.g. $5$ $6$ $1$ denotes that a node with key $5$ has only one child on the left with key $6$. You need to print the inorder traversal of the BST formed using the same nodes of the given tree. All keys are guaranteed to be pairwise distinct. ###Input Format:  The first line contains a single integer $T$ denoting the number of test cases  The first line of each test case contains an integer $M$  $M$ lines follow, each containing the keys of a node and its left and right child respectively ###Output Format: Print $T$ lines, each containing the inorder traversal of the BST of corresponding test case, separating each key by a space. ###Constraints  $1 \leq T \leq 5$  $1 \leq M \leq 10^5$  $key(node) \leq 10^9$  All keys are pairwise distinct ###Subtasks  40 points: $M \leq 10^3$  60 points: Original Constraints ###Sample Input 1 1 3 5 8 ###Sample Output 3 5 8 ###Explanation The inorder traversal of BST formed e.g. with root at $5$ and $3$ to its left and $8$ to its right will be $3\ 5\ 8$Author:  sonu_628 
Tags  sonu_628 
Date Added:  16012019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions