DEV Community

Sayani Mallick
Sayani Mallick

Posted on

Converting a sorted array into a binary search tree in C++

Let us see how to convert a sorted array into a binary search tree. Before that let us see what is a binary search tree.

What is a binary search tree?

A binary search tree is a node based data structure which has the following properties:

  1. The left sub-tree of a node contains elements lesser than that of the node
  2. The right sub-tree of a node contains elements greater than that of the node
  3. There are no duplicated values in the binary search tree.
  4. Each of the left sub-tree and right sub-tree follow the rules 1 and 2.

To create a binary search tree from a sorted array we first find the middle element and create the root. Then we use a recursive function to form the left and right sub-trees.

Code
The code snippet for creating a node:

Alt Text

The function for converting array to binary search tree:

Alt Text

The function for preorder traversal and printing of the binary search tree:

Alt Text

Hope this helps you!

Top comments (0)