Symantec Interview Question
Java DevelopersCountry: India
I use stack here
algo
buff[k]
k=0;
push(a[0])
i=1;
while ( end of array a[]) {
if(a[i]<top()) ;
push(a[i]);
else {
//maintain lowest element in top of the stack
while(a[i]>(buff[k++]=pop()));
push(a[i]);
}
}
complexity -> o(n)
finally if the array buff[] is sorted then its a preorder representation of BST
This problem can be solved recursively as mentioned by Anqshu
Essentially Preorder traversal of a tree looks something like this
Root {PreOder of Left Tree} {PreOrder Of Right Sub Tree}
Find the index of Right Sub tree using number immediate > then root.
And then recursively find preorder traversal of left and right tree
1. get the middle element of the array (mid element should be root),
2. partition left side and right side to new arrays aLeft and aRight,
from 0 - mid , mid + 1 - array.length
each array will represent a subtree of root, with their mid elements representing the root's left child (mid of aLeft) and right child (mid of aRight).
3. Call the function recursively until you reach an array size of 1. These will be the leaf elements
* If you wish to check if this is a balanced binary tree and elements are sorted properly, just check left child and right child while dividing the array using the rule:
if (ROOT > ROOT.LEFT && ROOT < ROOT.RIGHT)
Is it BT or BST, if it is BST, construction is as follows
1. make the first element as root
2. find index i where a[i] > a[0]
3. root->left = constructTree with nodes less than i
4. root->right = constructTree with nodes from i+1
I came up with this approach without extra space:
- angshu1986 May 03, 20151. take the first element, arr[0], as root.
2. For i=0 to length of array
i. find i where arr[i] > arr[0].
3. Split up arr into two sub arrays, 1 to (i-1) and i to length, the first being the left tree of root and the second the right tree.
4. Check if any element in second sub array has a value less than arr[0]. If found, return false indicating the tree cannot be formed.
5. Recursively call 1 to 4 for the two sub arrays.