Program to check if Tree is Binary Search Tree C++

Hello all, today we will write a program to check if given Binary Tree is Binary Search Tree or not. So let’s start with what properties a tree must satisfy so that it is a Binary Search Tree.

 

The tree satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Below is an example of Binary Search Tree:

binary search tree c++

 

How code works:

  • Perform a simple inorder traversal and keep the previous value of the node.
  • If the current node is smaller than the previous node then it is not a binary search tree
  • Otherwise it is a Binary search Tree.

 

Program to check if Tree is Binary Search Tree C++:

 

OUTPUT:

 

C++ program to implement AVL Tree

An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.

Definition of an AVL tree:

AVL tree

An AVL tree is a binary search tree which has the following properties:

  1. The sub-trees of every node differ in height by at most one.
  2. Every sub-tree is an AVL tree.

 

 

C++ program to implement AVL Tree:

OUTPUT:

 

 

C++ Program to Implement Floyd Warshall Algorithm

Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves.

Pseudo code:

 

Example:

Floyd Warshall algorithm

 

Prior to the first iteration of the outer loop, labeled k=0 above, the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found. Finally, at k=4, all shortest paths are found.

C++ program to implement Floyd Warshall Algorithm:

OUTPUT:

Program to implement Binary Search Tree C++

A Binary Search Tree is a Binary Tree data structure ( a tree in which each node has at most two children ) which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.
  • There must be no duplicate nodes.

Traversal of binary tree refers to the process of visiting each node one-by-one. For binary tree, we generally use the following 3 types of traversal:

  • Pre-Order
  1. Visit the root.
  2. Traverse the left subtree.
  3. Traverse the right subtree.
  • In-Order
  1. Traverse the left subtree.
  2. Visit the root.
  3. Traverse the right subtree.
  • Post-Order
  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the root.

binary search tree c++

For this tree, the Preorder traversal will be:
8, 3, 1, 6, 4, 7, 10, 14, 13

And the Inorder traversal will be:
1, 3, 4, 6, 7, 8, 10, 13, 14

And the Postorder traversal will be:
1, 4, 7, 6, 3, 13, 14, 10, 8

Here note that the Inorder traversal of a Binary Search tree results in an ascending order list.

Program to implement Binary Search Tree C++

 

OUTPUT:

Program to implement Depth First Search C++

What is Depth First Search?

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

depth first search c++

For example, in the above graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. Depth First Traversal of the following graph is 2, 0, 1, 3.

For Breadth First Search implementation –> see here

 

Program to implement Depth First Search C++:

 

OUTPUT:

Minimum Spanning Tree using Prim’s Algorithm

What is Spanning Tree?

The idea behind minimum spanning trees is simple: given a graph with weighted edges, find a tree of edges with the minimum total weight. What is a spanning tree? A graph that satisfies these three properties: connected, acyclic, and consisting of |V| – 1 edges. (In fact, any two of the three conditions imply the third condition.)

What this means in practice is that a spanning tree is a collection of edges that connect any two nodes via a single path. It’s probably easiest to understand a tree using the definition that a tree is both connected and acyclic; think about binary trees–every node in the tree is reachable, so it’s connected, and there are no cycles because you can’t go back up the tree.

Prim’s Algorithm:

Prim’s algorithm closely resembles Dijkstra’s algorithm because they both rely on a similar approach of finding the “next closest” vertex. Prim’s algorithm slowly grows a minimum spanning tree, starting from a single vertex and adding in new edges that link the partial tree to a new vertex outside of the tree.

Using the cut property, we know that if we have a partial tree, then to add a new vertex to the tree, all we actually need to do is find the vertex that is closest to the tree (the elements in the tree and the elements outside the tree are the two sets in the cut property, so we just choose the smallest edge bridging the two).

Download Source Code:
[adinserter block=”1″]

Download: prims.c

Program for Minimum Spanning Tree in C++ using Prim’s Algo.

 

OUTPUT:

minimum spanning tree using prims algorithm