A technical coding question included a question about binary trees and the various traversals (In-order, pre-order and post-order). If given the In-order (L, M, R) and Post-order (L, R, M), can you return the original tree? (M for mid instead of root because it starts with R). The two inputs are arrays of integers, the values at each node of the binary tree.

Question

A technical coding question included a question about binary trees and the various traversals (In-order, pre-order and post-order). If given the  In-order (L, M, R) and Post-order (L, R, M), can you return the original tree? (M for mid instead of root because it starts with R). The two inputs are arrays of integers, the values at each node of the binary tree.

Anonymous · Accepted Answer

I wasn't familiar with traversals and I tried to come up with a pattern by relating the positions of the numbers to which sub-trees they belonged to. My interviewer gave me a hint for Post-order, in that the root is always the last value so it is easy to isolate. 
I made a node and gave its value M.
I then identified the numbers in the L and R sub-trees from the root of the current tree or subtree, and made the algorithm recursive, calling the two versions of L and R (from the In-order and Post-order arrays) in the recursive calls. 
I made the left and right of the original node with value M equal to the function f(L1,L2) and f(R1,R2), respectively. I ran out of time to finish coding and my interviewer took a picture of the whiteboard.

Amazon

Amazon Interview Question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches