A tree with the property that each node has at most two child nodes (the left child and the right child). Useful in computer science and mathematics. Compare to a binary search tree and graph.

a mathematician picks an integer 'i' from the set {1-16} (integers) and a logician tries to search for the number with yes or no questions. in this particular case, the evil, conniving mathematician can lie once, or not at all, to hinder the logician.
a) create a binary tree where, in any situation, the logician can ask seven boolean questions or less and determine the mathematician's number.

A diagram might help illustrate a binary tree, and why it's so darn useful:

                      /   \
                     /     \
                    6      11
                   / \     / \
                  /   \   /   \
                 2    7  10   15

I'll go through how this comes about.

First, I inserted the value 9. Because it's the first value, it sits all proud at the top. Next comes 6. Because 6 is numerically less than 9, it goes on the left hand side of 9 (this is simply our way of conceptualising the structure. In reality, the top "node" (the name for an object in the tree) has a pointer to this value). Next, I insert 2. The logic process goes like this: 2 is less than 9, hence it wants to be on the left hand side of 9 somewhere. We then move down to 6, and see that 2 is also less than 6, so the value 2 is inserted on the left of 6. Next comes 7, which of course is less than 9, and greater than 6, hence its position (if a value is greater than its parent, it goes on the right in our conceptualisation).

You should now be able to see what happens with the three values to the right of 9.

Binary trees can be implemented for any data that can be greater or less than other bits of data of the same type. For instance, words are sorted lexicographically. Ant is said to be "lexicographically greater" than Zebra.

The true power of binary trees comes in searching them. If the data above was ordered linearly, I could have to scan up to seven values to find the one I want. With it arranged in a binary tree, the most I'll have to search is 3. Imagine what a difference this makes for massive amounts of data.

Log in or register to write something here or to contact authors.