Recover Tree from Pre Order traversal

Ninja
0/200
Average time to solve is 55m
profile
Contributed by
11 upvotes
Asked in company
Apple

Problem statement

Ninja has got a coding assignment. In this assignment, a preorder depth-first search (DFS) is run on the root of a binary tree.

At each node in this traversal, D dashes is given (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

It is also given to Ninja that if a node has only one child, that child is guaranteed to be the left child.

The output S of this traversal is given to Ninja. Your task is to help Ninja in recovering the tree and return its root.

Example

Let S = "1-2--3--4-5--6--7"

Here the tree for this preorder traversal will be like following:

So for this root will be 1, so the output tree will be 1 2 5 3 4 6 7 -1 - 1 -1 -1 -1 -1- 1 -1

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first and the only line of each test case contains a string S representing the preorder traversal of the input tree.
Output format : 
For each test case, you have to return the root of the tree.

Note: You do not need to take input or print anything. It already has been taken care of. Just implement the function.
Constraints : 
1 <= T <= 100
1 <= X <= 5000 where,X is the number of nodes in original tree
1 <= Y <= 10^9 where, Y is the value of node

Time limit: 1 sec
Sample input 1 :
2
1-2--3--4-5--6--7
1-5--3-6--4
Sample output 1 :
1 2 5 3 4 6 7 -1 - 1 -1 -1 -1 -1- 1 -1
1 5 6 3 -1 4 -1 -1 -1 -1 -1
Explanation :
Test case 1 :

The tree for this preorder traversal will be like following:


So the output tree would be 1 2 5 3 4 6 7 -1 - 1 -1 -1 -1 -1- 1 -1

Test case 2 :

The tree for this preorder traversal would be:


So the output tree will be 1 5 6 3 -1 4 -1 -1 -1 -1 -1
Sample Input 2 :
2
1-2--3---4-5--6---7
1-401--349---90--88
Sample Output 2 :
1 2 5 3 -1 6 -1 4 -1 7 -1 -1 -1 -1 -1
1 401 -1 349 88 90 -1 -1 -1 -1 -1
Hint

Think of preorder traversal of a tree and how you can use ‘-’ to recover the tree.

Approaches (1)
Using iterative stack

Algorithm:

  • Define one stack st
  • i := 0, n := size of S
  • lvl := 0, num := 0
  • while i < n, do −
    • for initialize lvl := 0, when S[i] is same as '-', update (increase lvl by 1), (increase i by 1), do −
      • do nothing
    • num := 0
    • while (i < n and S[i] is not equal to '-'), do −
      • num := num * 10 + (S[i] - '0')
      • (increase i by 1)
    • while the size of st > lvl, do −
      • delete element from st
    • temp = create a new Tree Node with num value
    • if not st is empty and not left off the top element of st is null, then −
      • left of the top element of st:= temp
    • otherwise when not st is empty, then −
      • right of the top element of st:= temp
    • insert temp into st
  • while the size of st > 1, do −
    • delete element from st
  • return (if st is empty, then NULL, otherwise top element of st)
Time Complexity

O(S) where S is the length of the string.

 

We are iterating over the whole string so the complexity will be O(S)


 

Space Complexity

O(n) where n is the number of nodes in the tree.

 

We are storing the nodes in a stack. So the complexity will be O(n)


 

Code Solution
(100% EXP penalty)
Recover Tree from Pre Order traversal
Full screen
Console