TreeTraversals
TCCC '03 Semifinals 4 · 2003-04-04 · by vorthys
Problem Statement
Consider a binary tree with N nodes, each labeled with a distinct integer between 1 and N, inclusive. We can convert the tree into a sequence of labels by traversing the tree in a particular order, but there are many possible orders. Two common orders are in-order traversal and breadth-first traversal, defined as follows:
- In-Order: Begin by visiting the root. As you visit each node, first recursively visit its left child (if it has one), then output the node's label, then recursively visit its right child (if it has one).
- Breadth-First: First output the label of the root, then the labels of the root's children, then the labels of the root's grandchildren, its great-grandchildren, and so on. Among nodes on the same level, output the labels from left to right.
1
/ \
2 4
/ / \
3 5 7
\
6
an in-order traversal would produce the sequence 3,2,1,5,6,4,7 and a breadth-first traversal would produce the
sequence 1,2,4,3,5,7,6.
Given the output of a particular traversal, we cannot always tell which of several possible trees we started with. However, given the output of both an in-order traversal and a breadth-first traversal of the same tree, we can uniquely reconstruct the tree. You are to write a method that takes the output of an in-order traversal, inOrder, and the output of a breadth-first traversal, breadthFirst, and returns the width of the tree, defined as the maximum number of nodes on any one level of the tree. For example, the tree above has width 3, achieved by the level containing the values 3, 5, and 7.
If we start with the output of an in-order traversal from one tree and a breadth-first traversal from a different tree, it is not always possible to reconstruct a single tree that is compatible with both sequences. If no tree exists that could have produced both traversals, return -1.
Constraints
- inOrder and breadthFirst contain the same number of elements (between 1 and 50, inclusive).
- Every element in inOrder and breadthFirst is between 1 and N, inclusive, where N is the number of elements in inOrder.
- No element appears more than once in inOrder or more than once in breadthFirst.
{ 3,2,1,5,6,4,7 }
{ 1,2,4,3,5,7,6 }
Returns: 3
The example above.
{1}
{1}
Returns: 1
{ 1,2,3 }
{ 1,2,3 }
Returns: 1
The tree 1 \ 2 \ 3
{ 1,2,3,4,5 }
{ 5,3,1,2,4 }
Returns: -1
{ 2,5,9,1,4,7,3,8,6 }
{ 4,9,3,5,1,7,8,2,6 }
Returns: 4
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TreeTraversals with a public method int width(vector<int> inOrder, vector<int> breadthFirst) · 37 test cases · 2 s / 256 MB per case