|
231. Given a file in which the data is stored in the form ... .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
231. Given a file in which the data is stored in the form ... .....
Question:
Given a file in which the data is stored in the form
ABC
_DEF
_GEH
XYZ
_PQR
__STY
Construct an nary tree out of it in O(n) time such that DEF and GEH are the children of ABC and XYZ is the sibling of ABC, PQR is child of XYZ and STY is child of PQR. The spaces after the beginning of a line specify the relation of a node to its predecessors.
maybe an answer:
1) Create a root X (Create a threaded binary tree)
2) Take a bit which represents the direction in which we have to add node
3) If bit is 0 then travel left else travel right
4) for ABC add to the left of X. (ABC right will be pointing to X)
5) DEF will be added to left of ABC since bit is still 0
6) GEH will be added to the right of ABC
7) We have XYZ which will be added to the right with bit set to 1
8) Now we will travel right and add nodes....
(Continued on next question...)
Other Interview Questions
| 