Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
it will just keep on adding nodes on the right of each node and we end up by having a link list! Is this something they are looking for?
Can't we do better by finding the middle of the given inorder traversal and make that as root and then keep on adding node on left and right from there?
I believe this is the correct answer? Breaking the array in two by the first number greater than root. O(n)
I guess if a interviewer asked this question, he won't give you an array to solve, instead he will give a stream of numbers.
3
\
9
\
20
and
3
/ \
9 20
will have the same Pre Order . We need In order to find the perfect tree.
I haven't seen an interesting answer to this yet. My solution is pretty simple and seems to work but I haven't tested it with many different shapes of BSTs.
After peeling off the current value from the input queue to create myself, I check if the next value on the queue is lower than me, and if so, I pass the remainder of the queue to my left child so it can create itself. Then I pass the remainder of the queue to my right child. In each recursive call, if I see that the next value for me is larger than my lineage I create nothing. Should be O(n) where n is the size of the tree.
The following code is member methods of a Java generic tree class with the usual Node nested class.
public void reconstruct(Queue<T> items) {
if (items.isEmpty()) {
return;
}
root = new Node<T>(items.remove());
if (!items.isEmpty() && (items.peek().compareTo(root.value) < 0)) {
root.left = reconstructSubtree(items, root.value);
}
root.right = reconstructSubtree(items, null);
}
private Node<T> reconstructSubtree(Queue<T> itemsLeft, T max) {
if (itemsLeft.isEmpty() ||
((max != null) && (itemsLeft.peek().compareTo(max) > 0))) {
return null;
}
Node<T> me = new Node<T>(itemsLeft.remove());
if (!itemsLeft.isEmpty() && (itemsLeft.peek().compareTo(me.value) < 0)) {
me.left = reconstructSubtree(itemsLeft, me.value);
}
me.right = reconstructSubtree(itemsLeft, max);
return me;
}
It is basically constructing BinaryTree given root, and the rest of the tree items.
Since we will need to go over the whole tree data it will be O(n), insertion to the tree is O(logn) hence the algorithm will be O(n) + O(log(n)) ==> log(n)
public class BTree {
Integer value;
BTree left;
BTree right;
public void add(Integer value) {
if (this.value == null) {
this.value = value;
left = new BTree();
right = new BTree();
} else {
if (value < this.value) {
left.add(value);
} else {
right.add(value);
}
}
}
void traversePre(BTree b) {
System.out.println(b.value);
traversePre(b.left);
traversePre(b.right);
}
static BTree conPreOrder(Integer[] array) {
Integer root = array[0];
BTree t = new BTree();
t.add(root);
for (int i = 1; i < array.length - 1; i++) {
t.add(array[i]);
}
return t;
}
public static void main(String[] args) {
Integer[] pre = { 10, 8, 7, 9, 20, 18, 25 };
BTree t = BTree.conPreOrder(pre);
t.traversePre(t);
}
}
If the pre-order stream/sequence has no specification, one can only use insertion to construct a BST in O(nlog(n)) time.
I think the problem is better described as: Given the pre-order traversal sequence of a binary search tree, build the tree.
This can be done in O(n) time and O(n) space using recursion. Start from the first element in the pre-order sequence, that's the root.
Move right in the sequence, enqueue all numbers that are less than the root. Recursively construct left child using the queue. Do the same for the right child.
public void BuildBSTUsingPreOrder(int[] preOrder, TreeNode node, int index)
{
if (index == 0)
{
node = new TreeNode(preOrder[0]);
index = 1;
}
if (index >= preOrder.Count)
return;
if (preOrder[index - 1] <= preOrder[index])
{
node.Right = new TreeNode(preOrder[index]);
if (index < preOrder.Length - 1 && preOrder[index - 1] > preOrder[index + 1])
BuildBSTUsingPreOrder(preOrder, node, index + 1);
else
BuildBSTUsingPreOrder(preOrder, node.Right, index + 1);
}
else
{
node.Left = new TreeNode(preOrder[index]);
if (index < preOrder.Length - 1 && preOrder[index - 1] < preOrder[index + 1])
BuildBSTUsingPreOrder(preOrder, node, index + 1);
else
BuildBSTUsingPreOrder(preOrder, node.Left, index + 1);
}
}
public class ConstructTreeFromPreorder {
static Node[] preOrderArray = new Node[6];
static int count = 0;
public static Node constructTree(Node[] preOrder) {
Stack<Node> stack = new Stack<Node>();
Node root = preOrder[0];
Node tmp = null;
stack.push(root);
for(int i = 1;i < preOrder.length;i++) {
tmp = null;
while (!stack.empty() && stack.peek().value < preOrder[i].value) {
tmp = stack.pop();
}
if(tmp != null) {
tmp.right = preOrder[i];
stack.push(preOrder[i]);
} else {
if(!stack.empty()) {
stack.peek().left = preOrder[i];
stack.push(stack.peek().left);
}
}
}
return root;
}
}
Since we are given a PRE-ORDER traversal, we know that the root node will be the first one that is traversed, then the left child and after that the right child.
so here, it doesnt even matter whether or not the list is sorted or not (which is will be since it is a preorder traversal of a BST which has the property that the left child < root < right child.
So, if the tree were like this
1
2 3
4 5 6 7
the preorder traversal would be
1 2 3 4 5 6 7
So, if it is an array,
index(left child) = 2*index(parent);
index(right child) = index(left child + 1);
So, we have
public Node CreateTreeFromPreOrder(int a[ ], int startIndex)
{
if(startIndex >= a.length)
return null;
int lchild, rchild;
Node x = new Node();
x. data = a[startIndex] ;
if(startIndex == 0)
lchild = 1;
else
lchild = 2*startIndex;
rchild = lchild + 1;
x.left = CreateTreeFromPreOrder(a, lchild);
x.right = CreateTreeFromPreOrder(a, rchild);
return x;
}
Processing Time = O(n)
Since we are given a PRE-ORDER traversal, we know that the root node will be the first one that is traversed, then the left child and after that the right child.
so here, it doesnt even matter whether or not the list is sorted or not (which is will be since it is a preorder traversal of a BST which has the property that the left child < root < right child.
So, if the tree were like this
1
2 3
4 5 6 7
the preorder traversal would be
1 2 3 4 5 6 7
So, if it is an array,
index(left child) = 2*index(parent);
index(right child) = index(left child + 1);
So, we have
public Node CreateTreeFromPreOrder(int a[ ], int startIndex)
{
if(startIndex >= a.length)
return null;
int lchild, rchild;
Node x = new Node();
x. data = a[startIndex] ;
if(startIndex == 0)
lchild = 1;
else
lchild = 2*startIndex;
rchild = lchild + 1;
x.left = CreateTreeFromPreOrder(a, lchild);
x.right = CreateTreeFromPreOrder(a, rchild);
return x;
}
Processing Time = O(n)
Oh come on...
1
2 3
4 5 6 7
Keep in mind that these numbers ONLY represent positions.. an actual BST would be sorted like this
4
2 6
1 3 5 7
In C++, with optimisation for inserting when the next item is less than the last item inserted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
class Node
{
public:
int item;
Node *left;
Node *right;
Node(int _item)
{
item=_item;
left = NULL;
right = NULL;
}
//Returns the node that was inserted.
//under some uses might want to add asserts to confirm is a binary tree at each itteration.
Node *insertNodeIntoBinaryTree(int value)
{
Node *currentNode = this;
while(1)
{
if(value<currentNode->item)
{
if(currentNode->left==NULL)
{
currentNode->left = new Node(value);
return currentNode->left;
}
currentNode=currentNode->left;
}
else if(value>currentNode->item)
{
if(currentNode->right==NULL)
{
currentNode->right = new Node(value);
return currentNode->right;
}
currentNode=currentNode->right;
}
else
{
//Curious. In this example, we should never get here.
//But in the real world we'd want to be able to cover trying
//to add a value that already exists.
//But unlike the returns above, this node might NOT be a leaf node.
//In other uses for this function, we might want to indicate this
//happened somehow.
return currentNode;
}
}
}
//Dumps in preorder. Not the best way to validate our tree, but it'll do
void dump()
{
printf("%d\n",item);
if(left!=NULL) left->dump();
if(right!=NULL) right->dump();
}
};
Node *createBinaryTreeFromPreOrderTraversal(int *values, int size)
{
if(size==0) return 0;
assert(values!=NULL);
Node *root = new Node(values[0]);
Node *currentNode = root;
for(int valueIndex=1; valueIndex<size; valueIndex++)
{
if(values[valueIndex]<currentNode->item)
{
//Can add to the left of current node (which we know to be a leaf)
currentNode->left=new Node(values[valueIndex]);
currentNode=currentNode->left;
}
else
{
//otherwise parse from the top of the tree
//An way would be for each node to hold the parent node.
//This way we could parse backwards from current node
//However, that's much more complicated and probably not any quicker
assert(values[valueIndex]!=currentNode->item);
currentNode=root->insertNodeIntoBinaryTree(values[valueIndex]);
}
}
return root;
}
int main(void)
{
int values[] = { 8,3,1,6,4,7,10,14,13 };
Node *root=createBinaryTreeFromPreOrderTraversal(values,9);
root->dump();
return 0;
}
- anon123 February 11, 2014