Tree ordering

Easy
0/40
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in companies
UberAmazon

Problem statement

You were jogging in the morning and found a Binary Tree ‘T’ containing ‘N’ nodes numbered from ‘1’ to ‘N’. You have just learned the Pre-Order Traversal, so you quickly performed the Pre-Order Traversal on the Binary Tree, but you did not like the outcome. So you decided to flip a minimum number of the nodes so that the Pre-Order Traversal of the new Binary tree matches the array ‘A’. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Note: Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node ‘1’ will have the following effect:

Detailed explanation ( Input/output format, Notes, Images )
Input Format- 
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer ‘N’, denoting the number of nodes in the BT.
The following line will contain the values of the tree’s nodes in the level order form ( -1 for 'NULL' node). Refer to the example for further clarification.
The next line contains 'N' space-separated integers denoting the array 'A'.

The input of the tree depicted in the image above will be like :

5 → represents the total number of nodes.
1 2 3 -1 -1 4 5 -1 -1 -1 -1 → represents the level order of Tree.
Explanation :
Level 1 :
The root node of the tree is 1.

Level 2 :
The left child of 1 = 2.
The right child of 1 = 3.

Level 3 :
The left child of 2 = null (-1)
The right child of 2 = null (-1)
The left child of 3 = 4
The right child of 3 = 5

Level 4:
The left child of 4 = null (-1)
The right child of 4 = null (-1)
The left child of 5 = null (-1)
The right child of 5 = null (-1)
Output Format- 
For each test case, print all the nodes you want to flip. You can print the nodes in any order. The total number of nodes must be minimum. If it is impossible to flip the nodes in the tree to make the pre-order traversal match A, Print -1.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints - 
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
Note- the sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec
Sample Input-1
2
3
1 3 2 -1 -1 -1 -1
1 2 3
3
2 1 3 -1 -1 -1 -1
1 2 3
Sample Output-1
1
-1
Explanation for Sample Input 1:
For test case 1:


From the image, we can see that if we flip at node 1, we will get the desired Pre-Order Traversal.

For test case 2:


From the image, we can see that we will never get the desired Pre-Order Traversal no matter which node we select.
Sample Input -2
2
4
1 3 2 4 -1 -1 -1 -1 -1
1 2 3 4
2
2 1 -1 -1 -1
1 2
Sample Output -2
1
-1
Hint

when should you flip at node ‘i’?

Approaches (1)
DFS

Approach: We will do a Pre-Order Traversal on the tree and if the left child of the current node does not match with the node that we need then we flip at the current node.

 

Algorithm:

  • Func dfs(current, ans, A, index).
    • If the current node is ‘Null’.
      • Return.
    • If the current node is not equal to A[index].
      • Clear ‘ans’.
      • Append -1 to ‘ans’.
      • Return.
    • Increment ‘index’ by 1.
    • If the left child of the current node is not equal to A[index].
      • Append the current node to ‘ans’.
      • Call the func dfs(root -> right, ans, A, index).
      • Call the func dfs(root -> left, ans, A, index).
    • Else.
      • Call the func dfs(root -> left, ans, A, index).
      • Call the func dfs(root -> right, ans, A, index).
  • Func Main().
    • Create an empty vector ‘ans’.
    • Create a variable ‘index’ and initialize it to 0.
    • Call the functions dfs.
    • If the first value in ans is ‘-1’.
      • Print -1.
    • Else.
      • Print all the values of ‘ans’.
Time Complexity

O(N), Where N is the number of nodes in the binary tree.

We are traversing in the BT containing ‘N’ nodes. Hence the overall complexity is O(N).

Space Complexity

O(N), Where N is the number of nodes in the binary tree.

The recursive stack can contain at most ‘N’ nodes of the BT. Hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Tree ordering
Full screen
Console