CareerCup

node getBST(int[] a, int start, int end)
{
	if(start>end)
		return null
		
	node x = new node(a[start]);
	
	int i=0;
	for(i=start+1;i<end;i++)
	{
		if(a[i]>a[start])
			break
	}
	
	x.left = getBST(a, start+1, i-1);
	x.right = getBST(a, i, end);
	
	return x;
	
}

getBST(a, 0, a.length-1)

You sure just given a preorder traversal is sufficient?

I suppose the interviewer gave you a pre-order for a BST, and you need to reconstruct that.

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);
    }
}

BST createBSTFromInorder(int[] inp, int start, int end)
{

	if(start > end)
		return null;

	BST node=new BST(inp[end]);

	int j=end-1;
	while(j>=0 && inp[j] <= inp[end])
		j--;
	
	node.right=createBSTFromInorder(inp,j+1,end-1);
	node.left=createBSTFromInorder(inp,start,j);

	return node;

}

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)

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;
}

it might work.

void f (node* t, int min, int max) {
  static int i = 0;
  if (min <= d[i] && d[i] <= max) {
    t = new node(d[i++]);
  }
  f(t->left, min, d[i]);
  f(t->right, d[i], max);
}