What is Binary Search Tree?

Differences among Binary Search, Binary Search Tree and Linear Search along with thier properties.

What is binary search?

A binary search is a method of searching for an element in a sorted array. It works by repeatedly dividing the array in half until the element is found or the array is empty.

Why is Binary Search SO IMPORTANT?

Binary search is an efficient algorithm for finding an item in a sorted list.

Features of Binary Search

• The binary search algorithm can be applied to a sorted array of data.
• The binary search algorithm halves the number of items to check with each iteration, making it a very efficient search method.
• The binary search algorithm can only be used if the data is sorted.

Examples of Binary Search:

When looking up a word in the dictionary, you would use a binary search. When searching for a value in a sorted list, you would use a binary search.

Binary search algorithm in Python

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

Binary search algorithm in JS

binary_search_algorithm = function(array, target) {
  var left = 0;
  var right = array.length - 1;
  var middle = Math.floor((left + right) / 2);
  while (array[middle] !== target && left <= right) {
    if (target < array[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
    middle = Math.floor((left + right) / 2);
  }
  if (array[middle] === target) {
    return middle;
  } else {
    return -1;
  }
}

What is the difference between Binary Search and Binary Search Tree?

Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search trees are data structures that allow efficient access to data via key-based searches.

What is Binary Search Tree?

A binary search tree is a data structure that allows fast lookup, insertion, and deletion of data items. It is a binary tree with the following properties:

• Each node in a binary search tree has two child nodes, one to the left and one to the right. The left child node contains data that is less than the data in the parent node, and the right child node contains data that is greater than or equal to the parent node.
• The data in each node is greater than or equal to the data in the left child and less than or equal to the data in the right child.
• The left and right subtrees are each binary search trees.

What are the Usages of Binary Search Tree?

The binary search tree data structure can be used for data in which the items have a natural order. For example, if the items are integers, the binary search tree can be used to determine which integer is larger or smaller. The binary search tree can also be used to find out if a particular item is in the tree.

Examples of Binary Search Tree:

A binary tree is a search tree if and only if it is both a binary tree and a search tree.

Python code for Binary Search Tree Algorithm:

def binary_search_tree(root):
    # check if the root is None
    if root is None:
        return True
    # check if the left subtree is a binary search tree
    if root.left is not None:
        if root.left.value > root.value:
            return False
        if root.left.value < root.value:
            return binary_search_tree(root.left)
    # check if the right subtree is a binary search tree
    if root.right is not None:
        if root.right.value < root.value:
            return False
        if root.right.value > root.value:
            return binary_search_tree(root.right)
    return True

JS code for Binary Search Tree Algorithm:

/* Prototype of binary search tree */
binary_search_tree.prototype.insert = function(value) {
  var node = new binary_search_tree.node(value);
  if (this.root == null) {
    this.root = node;
  } else {
    var current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left == null) {
          current.left = node;
          break;
        } else {
          current = current.left;
        }
      } else if (value > current.value) {
        if (current.right == null) {
          current.right = node;
          break;
        } else {
          current = current.right;
        }
      } else {
        break;
      }
    }
  }
  this.size++;
}

What is Linear Search Algorithm?

A linear search algorithm is a method for finding a target value within a list of values. It sequentially checks each element of the list until it finds an element that matches the target value or until it reaches the end of the list.

Python code for Linear Search Algorithm:

def linear_search(arr, n, x):
    for i in range(n):
        if arr[i] == x:
            return i
    return -1

Linear Search Algorithm in JS:

/* linear search Algorithm in JS*/
linearSearch = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === val) {
      return i;
    }
  }
  return -1;
}

Conclusion

The biggest difference between linear search and binary search is that, in the worst case, you have to check every element in the array when doing linear search, while you only need to check half of the elements when doing binary search. This is due to the fact that binary search uses a divide and conquer strategy, while linear search just goes through the elements one by one until it finds the desired element. The time complexity of binary search is therefore much better than linear search.