BINARY SEARCH TREE
This is a very special class of trees known as binary search trees. A binary search tree has binary nodes and the following additional property:
Given a node t, each node to the left is “smaller” than t, and each node to the right is “larger.” This definition applies recursively down the left and right subtrees. Figure 1 shows a binary search tree where characters are stored in the nodes.
Figure 1 also shows what happens if you do an inorder traversal of a binary search tree: you’ll get a list of the node contents in sorted order. In fact, that’s probably how the name inorder originated.
You may wonder what we mean by “smaller” and “larger” in our definition of binary search tree. This depends on the type of data being stored at the nodes. If, for instance, the data is integers, then the meaning of smaller and larger is obvious. More typically, though, the node data is some kind of structure, with one of the fields (called the key) used to make comparisons in a binary search tree.
A quick video to have a better (visual) understanding of a Binary Search Tree.
