## CapitalIQ Interview Question

Software Engineer / DevelopersThey solution is sweet and clever... surely the interviewer will be impressed... regarding Anna's question... b and e cannot have a common parent as b is parent of e.. so you have to check for that... correct me I am wrong... to make ravi solution more clear here is anthor ex...

10

5 12

3 6 11 13

4 15

so preorder : 10 3 4 5 6 11 12 13 15

inorder : 3 4 5 6 10 11 12 13 15

if you are looking for 3 and 11 then mark 3 and 11 in inorder array no now u have

inorder: 3 4 5 6 10 11

so when you check for 10 u get the solution right away... this is easy to determine as 3 and 11 are at same level...

now consider your looking for 11 and 15 then your inorder becomes: 11 12 13 15

so call inorder on 12 and then 13..

@hacker

Mayank's logic is correct ,it works .

For the above example

10

5 12

3 6 11 13

4 15

so preorder : 10 5 3 4 15 6 12 11 13

inorder : 4 3 15 5 6 10 11 12 13

if you are looking for 3 and 11 then mark 3 and 11 in inorder array no now u have

inorder: 3 15 5 6 10 11

so when you check for 10 u get the solution right away... this is easy to determine as 3 and 11 are at same level...

now consider your looking for 11 and 15 then your inorder becomes: 15 5 6 10 11

now check the preorder array u get 10 dividing the present inorder array 15 5 6 and 11 therefore 10 is he answer

Hi,

- Ravi Kant Pandey April 04, 2007if u have O(n) space you can do it in O(n) run time

traverse preorder the addresses of the nodes and store it.

then traverse inorder the addresses of the nodes and store it.

eg tree

a

b c

d e f

have PreOrder:a b d e c f

Inorder: d b e a c f

for two node ptrs eg d and c

mark the positions in inorder array and find first preorder ptr which seprates it into two

different parts of Inorder array

for above example first preorder ptr is a which seprates inorder into dbe and cf

so a is first commom ancester of d and c