Introduction To Binary Search Tree

A tree data structure is a way to hold data that looks like a tree when it’s visualized. For example:

All data points in a tree is called nodes. The top of the tree is called the root node and from the root it branches out into additional nodes called child node. Each of these child nodes may have more child nodes. Nodes with branches leading to other nodes are called the parent. And nodes that branches out from the parent is called child node and each children that parent of other tree makes their own sub-tree. Branches at the end of the tree which doesn’t have any child is called leaf nodes.

What is Binary Search Tree?

Why Use Binary Search Tree?

Binary search tree is also memory efficient because in array or in hash table we have take specific fixed amount of memory space and some of the indexes may remain empty. But in binary search tree we store the data by reference. As we add new data we take a chunk of memory and link to it.

When to Use Binary Search Tree?

Binary search tree will save the data in alphabetical order:

If we search for the name “orin’ , we’ll start at the root as the search key is less than the root (orin < paul) then we’ll go to the left child(nasrn). The left child less than the searched key (orin > nasrin). So, we’ll go to the right child which is the search key.

Time complexity

  • Deletion: O(log n)
  • Search: O(log n)

Software Engineer at LogMeIn

Software Engineer at LogMeIn