How to Store a Binary Search Tree to a File

A binary search tree is a data structure where records of data, called "nodes," have pointers to other nodes, called "children." This gives the nodes, when graphed out, a shape similar to a family tree. Nodes receive their place in the tree based on whether they would evaluate as greater than or less than other nodes. Left children are always less than their parent; right children always more.
Binary search trees are important in computer science because they can be both sorted and searched, on average, in O(n log n) time.

Things You'll Need

• Compiler
• Existing binary search tree

Instructions

1. Create a store function that receives the root node. Whenever you deal with trees in computer science, the most effective algorithm will nearly always be recursive and storing the tree to a file will be no exception. Here is a sample skeleton of the recursive store function (in Java).
   public void store(Node n) throws IOException {
   ...
   }

2. Write data on root node to file. This will use "pre-order traversal" (Root, Left Child, Right Child) to go through all the nodes in the tree, because this method of traversal will make it easiest to reconstruct the tree from the order of the nodes in the file. The recursive function now looks like this:
   public void store(Node n) throws IOException {
   write(savefile, n);
   }
   Store should call itself with the Left Child:
   public void store(Node n) throws IOException {
   write(savefile, n);
   store(n.left);
   }
   Store should call itself with the Right Child:
   public void store(Node n) throws IOException {
   write(savefile, n);
   store(n.left);
   store(n.right);
   }

3. Double-check that the function passes the recursive checklist. To prevent stack overflow errors, always check that a recursive function meets the following conditions:
   Does the function have an exit state? Yes, as long as the tree isn't of infinite depth, eventually it will reach a node that has neither a left or right child and will exit.
   Does the each iteration of the function move closer to the exit state? Yes, presuming that the tree is not circular and no node has one of its own ancestors as a child.
   The function passes the checklist.

4. Reconstruct from the file. When it comes time to load the tree back from the file, you will simply insert each node into the tree as it is loaded from the file using your standard insertion algorithm. This should start at the root and work its way down using pre-order traversal, placing the new node in the first empty space into which it will fit. This should reconstruct the tree exactly as it was originally composed in O(n log n) on average.

Tips & Warnings

• Catch StackOverflowException. Though its unlikely you'll use all the stack space in a correctly written recursive function, if you are working with Java, be sure to catch the StackOverflowException with all your recursive functions, so you can deal with them cleanly. Catch the IOException. If writing out to the file fails somewhere along the way, better to know when the file is written than when a corrupted file is being read.

• Don't store pointers to file. A simple mistake would be directly save the left and right child variables from each node. In most languages, these would be implemented as pointers to memory addresses. Needless to say, these memory addresses will change from one run to another, so storing them in a file would be pointless.

References

• Binary Search Tree at NIST Dictionary of Algorithms and Data Structures

Resources

• Read this Article in Spanish