Related:
https://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/
Solution to the problem is similar to isBST Max-Min Solution.
“Your root value can have any value between -∞ to + ∞, say it is 30 here, When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between — ∞ and 30. likewise
So the idea is Pass the minimum and maximum values between which the node’s value must lie.
- Example: int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
- First element in the preorder[] will definitely be the root, which is 20 here.
- we start with the range minimum = Integer.MIN_VALUE and maximum = Interger.MAX_VALUE, so your root can take any value between this range.
- So when putting the left node of 20(root), it must lie within the range to minimum = Integer.MIN_VALUE and maximum = 20, so check the next element in the preorder[], if it lies in this range, make it the left child to the root, else it must the the right chlid of the root and so on. See the figure for better understanding. ( see the execution sequence)
- Solve it recursively.
Time Complexity: O(n)
public int pIndex = 0;
public Node constructTree(int[] preorder, int data, int min, int max) {
if (pIndex < preorder.length) {
if (preorder[pIndex] > min && preorder[pIndex] < max) {
Node root = new Node(data);
pIndex++;
if (pIndex < preorder.length) {
// nodes lies between min and data will create left subtree
root.left = constructTree(preorder, preorder[pIndex], min,
data);
// nodes lies between data and max will create right subtree
root.right = constructTree(preorder, preorder[pIndex],
data, max);
}
return root;
}
}
return null;
}
- Example: int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 };
- Use Stack.
- First element in the preorder[] will definitely be the root, which is 20 here.
- Create a node with data 20 and push it in Stack.
- Now take the next element (say ‘data’) from the preorder sequence.
- If ‘data’ is greater than the top item in the stack then keep popping out the nodes from the stack, keep storing it in temp node till the top node in stack is less than the ‘data’.
- create a node with ‘data’ and add it to the right of temp node and push the temp node to stack.
- If ‘data’ is less than the top item in the stack then create a node with ‘data’ and add it to the left of top node in stack and push it in the stack.
- Repeat the above two steps till all the elements in preorder[] is over.
- return the root
Time Complexity: O(n)
public Node constructTree(int[] preorder) {
Stack<Node> s = new Stack<Node>();
Node root = new Node(preorder[0]);
s.add(root);
for (int i = 1; i < preorder.length; i++) {
Node x = null;
while (!s.isEmpty() && preorder[i] > s.peek().data) {
x = s.pop();
}
if (x != null) {
x.right = new Node(preorder[i]);
s.push(x.right);
} else {
s.peek().left = new Node(preorder[i]);
s.push(s.peek().left);
}
}
return root;
}
Time Complexity: O(n^2)
Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.
Assume we have the following BST:
_30_ / \ 20 40 / / \ 10 35 50
Pre-order traversal: When we read the BST back from the file, we are always able to create the parent node before creating its child nodes.
We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.Prefer pre-order; Binary search tree with min and max pair.
http://blog.csdn.net/nicaishibiantai/article/details/45006517
preorder traversal将bst存下来。
如何恢复？依然preorder。母节点的数值决定了子节点可以存储的范围，所以我们拿到一个新的数字时，看他是不是在母节点的规定范围内；否则就继续到母节点的另外一个子树中尝试。
public static BST readBST(String fileName) throws Exception {
BufferedReader fin = new BufferedReader(new FileReader(fileName));
data = Integer.parseInt(fin.readline());
bst = new BST();
bst.root = new Node(-1, null, null);
buildBST(bst.root, new int[] {data,}, Integer.MIN_VALUE, Integer.MAX_VALUE, fin);
}
private void buildBST(Node node, int[] data, int low, int high, BufferedReader fin) {
if (data[0] > low && data[0] < high) {
node.data = data[0];
try {
data[0] = Integer.parseInt(fin.readline());
if (data[0] > low && data[0] < node.data) {
node.left = new Node(-1, null, null);
buildBST(node.left, data, low, node.data, fin);
}
if (data[0] > node.data && data[0] < high) {
node.right = new Node(-1, null, null);
buildBST(node.right, data, node.data, high, fin);
}
} catch (Exception e) {}
}
}
void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) {
int val = insertVal;
p = new BinaryTree(val);
if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}
void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}
http://sudhansu-codezone.blogspot.com/2012/02/saving-bst-to-file.htmlRead full article from Saving a Binary Search Tree to a File | LeetCode
