Binary Search Tree
Overview
We already know what Binary Tree is so we have a solid foundation to move on and learn one of the most common types of a binary tree (also very common in job tech inteview questions) - Binary Search Tree!
As already mentioned - Binary Search Tree is a type of Binary Tree but with a couple additional simple properties:
- The values of all child nodes to the left are lesser than their parent
- And the values of all child nodes to the right are greater than their parent
It shouldn't be mistaken with a max heap - here the root is not the highest value node, rather - it's the 'mid' ground. And whatever is to the left of the root is smaller, whatever is to the right - is bigger.
The main purpose of the Binary Search Tree is, of course, very efficient searching as well as performing of insertion/deletion operations.
Considering the 'Search' in its name, it would be a shame to not take a look at how searching in a Binary Tree works.
Thankfully, it's generally simple and it's clearly visible from the animation. Just compare the element you search for, to the root first. If it's lesser, move to the left child. If it's lesser again, move to the next left child. And if it's greater, move to the right child. The result is - a very quick search.
And there are many applications for Binary Search Trees - like database indexing, searching algorithms, spell checking, caching and many others... and of course - to be used as a job interview question :)
Code
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return root
def search(root, target):
if root is None or root.value == target:
return root
if target < root.value:
return search(root.left, target)
else:
return search(root.right, target)
def build_binary_search_tree(arr):
root = None
for value in arr:
root = insert(root, value)
return root
arr = [60, 40, 10, 7, 15, 50, 45, 90, 70, 75, 90]
root = build_binary_search_tree(arr)
target_value = 15
result_node = search(root, target_value)
if result_node:
print(f"{target_value} found in the binary search tree.")
else:
print(f"{target_value} not found in the binary search tree.")
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function insert(root, value) {
if (root === null) {
return new TreeNode(value);
}
if (value < root.value) {
root.left = insert(root.left, value);
} else if (value > root.value) {
root.right = insert(root.right, value);
}
return root;
}
function search(root, target) {
if (root === null || root.value === target) {
return root;
}
if (target < root.value) {
return search(root.left, target);
} else {
return search(root.right, target);
}
}
function buildBinarySearchTree(arr) {
let root = null;
for (const value of arr) {
root = insert(root, value);
}
return root;
}
const arr = [60, 40, 10, 7, 15, 50, 45, 90, 70, 75, 90];
const root = buildBinarySearchTree(arr);
const targetValue = 15;
const resultNode = search(root, targetValue);
if (resultNode) {
console.log(`${targetValue} found in the binary search tree.`);
} else {
console.log(`${targetValue} not found in the binary search tree.`);
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree {
public static TreeNode insert(TreeNode root, int value) {
if (root == null) {
return new TreeNode(value);
}
if (value < root.value) {
root.left = insert(root.left, value);
} else if (value > root.value) {
root.right = insert(root.right, value);
}
return root;
}
public static TreeNode search(TreeNode root, int target) {
if (root == null || root.value == target) {
return root;
}
if (target < root.value) {
return search(root.left, target);
} else {
return search(root.right, target);
}
}
public static TreeNode buildBinarySearchTree(int[] arr) {
TreeNode root = null;
for (int value : arr) {
root = insert(root, value);
}
return root;
}
public static void main(String[] args) {
int[] arr = {60, 40, 10, 7, 15, 50, 45, 90, 70, 75, 90};
TreeNode root = buildBinarySearchTree(arr);
int targetValue = 15;
TreeNode resultNode = search(root, targetValue);
if (resultNode != null) {
System.out.println(targetValue + " found in the binary search tree.");
} else {
System.out.println(targetValue + " not found in the binary search tree.");
}
}
}
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
TreeNode* insert(TreeNode* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->value) {
root->left = insert(root->left, value);
} else if (value > root->value) {
root->right = insert(root->right, value);
}
return root;
}
TreeNode* search(TreeNode* root, int target) {
if (root == NULL || root->value == target) {
return root;
}
if (target < root->value) {
return search(root->left, target);
} else {
return search(root->right, target);
}
}
TreeNode* buildBinarySearchTree(int arr[], int size) {
TreeNode* root = NULL;
for (int i = 0; i < size; i++) {
root = insert(root, arr[i]);
}
return root;
}
int main() {
int arr[] = {60, 40, 10, 7, 15, 50, 45, 90, 70, 75, 90};
int size = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = buildBinarySearchTree(arr, size);
int targetValue = 15;
TreeNode* resultNode = search(root, targetValue);
if (resultNode != NULL) {
printf("%d found in the binary search tree.\n", targetValue);
} else {
printf("%d not found in the binary search tree.\n", targetValue);
}
return 0;
}
class TreeNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = $value;
$this->left = null;
$this->right = null;
}
}
function insert($root, $value) {
if ($root === null) {
return new TreeNode($value);
}
if ($value < $root->value) {
$root->left = insert($root->left, $value);
} else if ($value > $root->value) {
$root->right = insert($root->right, $value);
}
return $root;
}
function search($root, $target) {
if ($root === null || $root->value === $target) {
return $root;
}
if ($target < $root->value) {
return search($root->left, $target);
} else {
return search($root->right, $target);
}
}
function buildBinarySearchTree($arr) {
$root = null;
foreach ($arr as $value) {
$root = insert($root, $value);
}
return $root;
}
$arr = [60, 40, 10, 7, 15, 50, 45, 90, 70, 75, 90];
$root = buildBinarySearchTree($arr);
$targetValue = 15;
$resultNode = search($root, $targetValue);
if ($resultNode !== null) {
echo $targetValue . " found in the binary search tree.\n";
} else {
echo $targetValue . " not found in the binary search tree.\n";
}