Binary Search Tree - Code

Binary Search Tree

The following C++ code will explains the implementation of Binary Search Tree.
The following implementation is in object oriented using the Tree class and tree object. 
The implemented ADT functions of Binary Search Tree are insert and search.

Binary Search Tree

Introduction to Tree
Tree is used in data structure. A tree is used for quick search and can store unordered data.

A tree diagram is a useful tool to list all the logical possibilities of a sequence of events where each event can occur in a finite number of ways.

A tree consists of a root, a number of branches leaving the root, and possible additional branches leaving the end points of other branches.
A tree is normally constructed from left to right. A vertex of degree 1 in a tree is called a terminal vertex or a leaf node and a vertex of degree greater than 1 in a tree is called an internal vertex or a branch. The nodes at the lowest levels of the tree (the ones with no sub-trees) are called leaves.

Depth First Search

What is Graph?
A graph is just a set of vertices (nodes), together with edges (connections) between some pairs of nodes. If the connections have a direction, the graph is said to be “directed graph”, otherwise the graph is said to be “undirected graph”.

A graph G = (V, E) with V, i.e. set of vertices and E, i.e. set of edges.

Searching a graph: Systematically follow the edges of a graph to visit the vertices of the graph. And is used to discover the structure of a graph.

Standard graph searching algorithms are

• Depth First Search (DFS)
• Breadth First Search (BFS)

Problem Statement
Deeply search a graph to make logical tree. 
Depth First Search
Depth first is an algorithm for traversing or searching a tree. It explore edges out of the most recently discovered vertex v. When all edges of v have been explored, backtrack to explore other edges leaving the vertex from which v was discovered (its predecessor). 

 “Search as deep as possible first.”

Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree.