Discussion
The in-order traversal output and pre-order traversal output of a binary tree are same, then the binary tree is :
Answer: B
The binary tree is right skewed.
In-order traversal visits left subtree, node, right subtree; pre-order visits node, left subtree, right subtree. The two orders can only agree if no node has a left subtree, because a left subtree would be visited before its node in in-order but after it in pre-order. Every node then has only a right child, which is a right-skewed tree; both traversals list the nodes from the root downwards.
In a left-skewed tree the in-order output is the reverse of the pre-order. A balanced or complete tree with more than one level has left children, so its two outputs differ.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development