Apple Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Inorder traversal of T1 will be reverse of inorder traversal of T2, if they are mirror image of each other.
- Do the inorder traversal of T1 and store the result in a stack.
- Do the inorder traversal of T2 and compare the results with the popped elements from the
stack
Question never said it was a binary tree. By definition tree is a connected graph with no cycles with one vertex named a root.
I don't like recursive solutions for this one as in this case for very deep trees we might ran out of stack quite fast. While in breadth search solution our memory complexity is bounded by "widest" part of the tree.
step 1: do In order traversal for first tree and store the result in one array.
step 2: start in order traversal for the second tree and compare the node value with result array, if both match continue the traversal and both tree are completed in traversal, they are mirror image trees or else stopped...and the result is not matched..
1. Suppose we have trees p and q.
2. Swap the left and right nodes of q.
3. Check is p and q are structurally equivalent
4. Swap the left and right nodes of q to get the original tree back.
- Prakash October 03, 2013