Expedia Interview Question
Software Engineer in TestsCountry: United States
For BST Pre Order is sufficient. Make a tree, write it's preorder and try to make some other tree.
Correct, we can construct a BST. If tree was known to be a BST we now have two expressions to determine left and right unknowns :)
But if its not already known, as in the question then we can't construct the same tree.
@rajanikant.malviya: one of the two traversals should a 'inorder' to get the actual tree.
public static void ConstructBSTusingPreOrder(TreeNode node, int[] PreOrderArr)
{
int numofNodes = PreOrderArr.Length-1;
if (node == null)
{
buildBST(ref node, PreOrderArr[0]);
}
for (int i = 1; i < numofNodes; i++)
{
buildBST(ref node, PreOrderArr[i]);
}
}
public static void buildBST(ref TreeNode node, int i)
{
if (node == null)
{
node = new TreeNode(i);
}
else if (node.data < i)
{
buildBST(ref node.right, i);
}
else
{
buildBST(ref node.left, i);
}
}
Is this correct...it works fine though
Node* constructBSTWithPreOrderVals(int* vals, int left, int right){
if(left > right){
return NULL;
}
int rightChildValIndex = left+1;
//the right child would be the value bigger than a[left]
while(rightChildValIndex <= right){
if(a[left] < a[rightChildValIndex]){
//we found the right child
break;
}
}
//construct the root node here
Node* root = new Node(a[left]);
//recursively construct the left tree
root->left = constructBSTWithPreOrderVals(vals, left+1, rightChildValIndex-1);
//recursively construct the right tree
root->right = constructBSTWithPreOrderVals(vals, rightChildValIndex, right);
return root;
}
//test
int vals[] = {35, 20, 10, 5, 11, 25, 21, 30, 60, 45, 70, 65, 72};
Node* root = constructBTWithPreOrderVals(vals, 0, sizeof(vals)/sizeof(int)-1);
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
enum TraversalType {
PREORDER, INORDER, POSTORDER;
}
public class ConstructTreeBack {
static Node root = new Node();
static TraversalType traversalType;
static void formSubTrees(List<Integer> treeList) {
List<Integer> leftSubTree = new ArrayList<Integer>();
List<Integer> rightSubTree = new ArrayList<Integer>();
Iterator<Integer> it = treeList.iterator();
int rootNodeVal = root.getValue();
while (it.hasNext()) {
int nodeVal = it.next();
if (rootNodeVal > nodeVal) {
leftSubTree.add(nodeVal);
} else if (rootNodeVal < nodeVal) {
rightSubTree.add(nodeVal);
}
}
if (leftSubTree.size() <= 3) {
Node left = formNode(leftSubTree);
root.setLeftNode(left);
} else {
formSubTrees(leftSubTree);
}
if (rightSubTree.size() <= 3) {
Node right = formNode(rightSubTree);
root.setRightNode(right);
} else {
formSubTrees(rightSubTree);
}
if (traversalType.equals(TraversalType.PREORDER)) {
System.out.println("PRE ORDER :: " + root);
} else if (traversalType.equals(TraversalType.INORDER)) {
System.out.println("In ORDER :: " + root);
} else if (traversalType.equals(TraversalType.POSTORDER)) {
System.out.println("POST ORDER :: " + root);
}
}
static Node formNode(List<Integer> treeList) {
Node node = new Node();
if (traversalType.equals(TraversalType.PREORDER)) {
if (null != treeList.get(0)) {
node.setValue(treeList.get(0));
}
if (null != treeList.get(1)) {
node.setLeftNode(new Node(treeList.get(1)));
}
if (null != treeList.get(2)) {
node.setRightNode(new Node(treeList.get(2)));
}
} else if (traversalType.equals(TraversalType.INORDER)) {
if (null != treeList.get(1)) {
node.setValue(treeList.get(1));
}
if (null != treeList.get(0)) {
node.setLeftNode(new Node(treeList.get(0)));
}
if (null != treeList.get(2)) {
node.setRightNode(new Node(treeList.get(2)));
}
} else if (traversalType.equals(TraversalType.POSTORDER)) {
if (null != treeList.get(2)) {
node.setValue(treeList.get(2));
}
if (null != treeList.get(0)) {
node.setLeftNode(new Node(treeList.get(0)));
}
if (null != treeList.get(1)) {
node.setRightNode(new Node(treeList.get(1)));
}
}
return node;
}
public static void main(String[] args) {
int rootNodeVal = 0;
List<Integer> treeList;
/*PRE ORDER TRAVERSAL*/
Integer treeArrPreOrder[] = { 4, 2, 1, 3, 6, 5, 7 };
rootNodeVal = treeArrPreOrder[0]; root.setValue(rootNodeVal);
root.setRoot(true);
treeList = Arrays.asList(treeArrPreOrder);
traversalType = TraversalType.PREORDER;
formSubTrees(treeList);
/*IN ORDER TRAVERSAL*/
Integer treeArrInOrder[] = { 1, 2, 3, 4, 5, 6, 7 };
int rootIndex = 3;
root.setValue(treeArrInOrder[rootIndex]);
root.setRoot(true);
treeList = Arrays.asList(treeArrInOrder);
traversalType = TraversalType.INORDER;
formSubTrees(treeList);
/*POST ORDER TRAVERSAL*/
Integer treeArrPostOrder[] = { 1, 3, 2, 5, 7, 6, 4 };
rootNodeVal = treeArrPostOrder[treeArrPostOrder.length - 1];
root.setValue(rootNodeVal); root.setRoot(true);
treeList = Arrays.asList(treeArrPostOrder);
traversalType = TraversalType.POSTORDER;
formSubTrees(treeList);
}
}
Can construct "A Tree" but not the same tree for which the pre-order traversal is given.
- rajanikant.malviya September 28, 2012Atleast two kinds of traversals are required to construct back the tree, reason?
---- Each node has two nodes "letf" and "right" ie, two unknowns thus atleast two expression / fittings required to find them :)