CareerCup

Forgot to mention BST is not balanced

can't we simply say find the height of a bst given its pre-order traversal without actually creating the original tree??

are these two same?

1. Read a chunk of integers from the file.
2. While building the BST and keeping track of the current height, keep a stack of incompleted parents.
3. If you are done with the chunk of integers read in the next chunk. If the stack becomes too big, save it to a file, and start a new stack.
4. When all the leaf nodes are done in a subtree, pop the stack to go back to the appropriate parent. If the stack is empty, load the previously saved stack file.

As the tree may not be balanced. How can we build a tree with only pre-order?
As I know, we need 2 orders at least to build a BST.

So does it seem like an unsolved problem in reasonable time.

Here is my soluion:

if its BST of integers, the preorder will look like this

ex:
4
26
1357

preorder: 4-2-1-3-6-5-7

1. the first number to read is denoted as head.
2. create a new variable called leftheight and init to zero.
3. continue reading integers from the stream.
4. check if the number read just now, is smaller than the number read before it.
5. if Yes, leftheight++. goto step 4.
6. If No, check if the integer read now is also greater than head (read in step 1)
7. If Yes, the new number we read just now is head of right subtree. repeat steps 1-6 to get height of right subtree and compare it with leftheight, whichever is the highest is the height of the tree. algorithm ends.
8. If No, we have just completed a subtree of a main tree and now moving to the right part of it.
From here on, leftheight should be updated only if the righttree reports more height then already recorded value.

i will try to comeup with a program (mostly recursive one to solve this)