# RECTREE - Editorial

Prerequisites :- Binary Trees, Level Order Traversal.

Problem :- Given a level order traversal of a complete binary tree which has N nodes numbered from 1 to N. The label of the i-th node in the traversal is Ai. You need to reconstruct that tree.

Solution Approach :- We can use a level order traversal approach to reconstruct the binary tree. It utilizes a queue to keep track of the nodes and their children during the reconstruction process.

A more detailed explanation of the reconstruct() function:

• The function initializes a queue and the root of the binary tree using the first element of the traversal array.
• It then iterates through the remaining elements of the array.
• For each element, it creates a new node with the value from the traversal array and assigns it as the left child of the current node (if the value is not -1).
• If there are more elements in the traversal array, it repeats the process for the right child.
• The queue helps in keeping track of the nodes and their children during the reconstruction process.

Time Complexity: The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. The function processes each element in the level order traversal array once.

Space Complexity: The space complexity is O(N), where N is the number of nodes in the binary tree. This is due to the space required for the queue, which can have at most N/2 nodes in a complete binary tree. The new nodes created during the reconstruction also contribute to the space complexity.