Interview Questions

In a unsorted binary tree, preorder, postorder.......

Microsoft Interview Questions and Answers


(Continued from previous question...)

113. In a unsorted binary tree, preorder, postorder.......

Question:
In a unsorted binary tree, preorder, postorder an InOrder traversal has provided in the form of Array.
Need to verify all the three arrays are refering to the same binary tree.



maybe an answer:


it can be done with a recursive pattern. You get three arrays with corresponding start and end (both inclusive) indices. They are the inorder, preorder and postorder representations of the tree. The algorithm is like:-

- Match the start element of preorder with last element of postorder. If match is successful, search this element in the inorder representation using linear search and keeping duplicates in mind. If found, use it as potential root element.
- Use the location of potential root in inorder representation to determine the number of nodes in left and right subtrees
- Recurse on inorder, preorder and postorder representations of left and right subtrees. If recursion on subtrees fails then find another potential root in the inorder representation and repeat

This is easy to follow in the following C# implementation
// helper method for linear search
public static int SearchFirst(int[] a, int start, int end, int key)
{
for (int i = start; i <= end; i ++)
{
if (a[i] == key)
return i;
}

return -1;
}

public static bool Verify(int[] inOrder, int inStart, int inEnd,
int[] preOrder, int preStart, int preEnd,
int[] postOrder, int postStart, int postEnd)
{
// empty traversals imply empty trees
if (inOrder == null || preOrder == null || postOrder == null)
{
if (inOrder == null && preOrder == null && postOrder == null)
return true;
else
return false;
}

if (inStart > inEnd || preStart > preEnd || postStart > postEnd)
{
if (inStart > inEnd && preStart > preEnd && postStart > postEnd)
return true;
else
return false;
}

// if we reach here then we have non empty traversals

// verify root in preOrder and postOrder
if (preOrder[preStart] != postOrder[postEnd])
return false;

int i = inStart;

while ((i = SearchFirst(inOrder, i, inEnd, preOrder[preStart])) != -1)
{
int leftLength = i - inStart;
int rightLength = inEnd - i;

// verify left and right subtrees
if (Verify(inOrder, inStart, i - 1,
preOrder, preStart + 1, preStart + leftLength,
postOrder, postStart, postStart + leftLength - 1) &&
Verify(inOrder, i + 1, inEnd,
preOrder, preStart + leftLength + 1, preEnd,
postOrder, postStart + leftLength, postEnd - 1))
return true;

i++;
}

return false;
}

(Continued on next question...)

Other Interview Questions