Last Updated: 11 Apr, 2021

Recover Tree from Pre Order traversal

Ninja

Asked in company

Solve now

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

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

Solve now

Approaches

01 Approach

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)

Solve now