CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-treepreorder
sachin thakur
sachin thakur

Reputation: 101

Construct Binary Search Tree from PreOrder

Way to construct binary search tree from preorderTransaversal.Please suggest if there is any suggestion.

Node constructTreeFromPreorder(int[] arr,int start,int end)
{
if(arr==null){
    return null;
}else{
    if(start>end){
        return null;
    }
    int element=arr[start];
    Node node=new Node(element); // create node
    if(start==end){
        return node;
    }
    int index=start+1;
    for(int i=index;i<=end;i++){
          index=i;
        if(arr[i]>element){
            break;
        }
    }
    node.left=constructTreeFromPreorder(arr, start+1, index-1);
    node.right=constructTreeFromPreorder(arr, index, end);
    return node;
}

Upvotes: 1

Views: 288

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134125

There are multiple binary trees that correspond to any preorder traversal. For example, consider the preorder traversal [2,1,3]. That is the preorder traversal for all of these trees:

  2         2     2          2      2
1   3     1         1      1          1
        3         3          3          3

You need more information than just a preorder traversal if you want to uniquely describe a binary tree.

Added after you modified the question: Of those, only the first is a valid binary search tree. I'm not sure if there are multiple BSTs for a given preorder traversal.

If there are duplicate items in the list, then there can be multiple trees for any given preorder traversal.

Upvotes: 2

Related Questions