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: