What is 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.

Figure 1: Binary Search Tree

A quick video to have a better (visual) understanding of a Binary Search Tree.

  1. Binary Search Tree Traversal « Encrypt3d
  2. How to search in a Binary Search Tree? « Encrypt3d
  3. How to count number of nodes in a Binary Search Tree? « Encrypt3d

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: