Binary Search Tree

Today I wanted to talk about Binary Search Tree (BST). Basically, a binary search tree is a data structure used in computer science for organizing and storing data in a sorted manner.

If you think of a tree, it has many branches. One branch leads to another branch, and that branch splits into others. The same concept applies to a binary search tree.

In a BST, each node has at most two children, referred to as the left child and the right child. The tree is structured in such a way that:

  • The left subtree of a node contains only nodes with values less than the node’s value.
  • The right subtree of a node contains only nodes with values greater than the node’s value.
  • Both the left and right subtrees must also be binary search trees.

This structure allows for efficient searching, insertion, and deletion operations. When you want to find a particular value, you start at the root and move left or right depending on whether the value you’re searching for is less than or greater than the current node’s value. This process continues until you find the value or reach a leaf node.

Binary search trees are commonly used in various applications such as:

  • Databases for quick lookups, insertions, and deletions
  • Sorting algorithms
  • Implementing associative arrays (like maps and dictionaries)
  • Managing sorted data in dynamic scenarios

The efficiency of a binary search tree depends heavily on its shape. Ideally, a balanced BST maintains a height of log(n), where n is the number of nodes, resulting in average-case time complexities of O(log n) for search, insert, and delete operations. However, in the worst-case scenario, if the tree becomes unbalanced (resembling a linked list), these operations can degrade to O(n).

To maintain balance, self-balancing binary search trees such as AVL trees and Red-Black trees are used. These trees perform additional operations to ensure the tree remains balanced after insertions and deletions, thereby maintaining efficient performance.

Understanding the binary search tree is fundamental for any computer scientist or software engineer, as it forms the basis for more complex data structures and algorithms.

There are two important algorithm used to traverse or search trees and graph data structures. They are:

  1. BFS (Breadth-First Search)
  2. DFS (Depth-First Search)

Each method has its unique traversal order and use cases. Here’s a detailed explanation

Breadth-First Search (BFS)

BFS is a traversal algorithm that starts at the root of the tree (or an arbitrary node in a graph) and explores all the neighbor nodes at the present depth level before moving on to nodes at the next depth level. This algorithm uses a queue data structure to keep track of the nodes to be explored next.

Steps:

  1. Start at the root node.
  2. Enqueue the root node.
  3. While the queue is not empty:
    • Dequeue the front node.
    • Process the dequeued node (e.g., print its value).
    • Enqueue all the unvisited neighbors of the dequeued node.

Use Cases:

  • Finding the shortest path in unweighted graphs.
  • Level-order traversal of a tree.
  • Networking broadcasting.

Depth-First Search (DFS)

DFS is a traversal algorithm that starts at the root of the tree (or an arbitrary node in a graph) and explores as far as possible along each branch before backtracking. This algorithm uses a stack data structure, either implicitly through recursion or explicitly through an iterative approach.

Steps:

  1. Start at the root node.
  2. Push the root node onto the stack.
  3. While the stack is not empty:
    • Pop the top node.
    • Process the popped node (e.g., print its value).
    • Push all the unvisited neighbors of the popped node onto the stack.

Variants:

  • Pre-order Traversal: Visit the root node first, then recursively do a pre-order traversal of the left subtree, followed by a pre-order traversal of the right subtree.
  • In-order Traversal: Recursively do an in-order traversal of the left subtree, visit the root node, and finally do an in-order traversal of the right subtree.
  • Post-order Traversal: Recursively do a post-order traversal of the left subtree, followed by the right subtree, and then visit the root node.

Use Cases:

  • Topological sorting.
  • Solving puzzles with a single solution (e.g., mazes).
  • In-order traversal to retrieve data in sorted order from a binary search tree.

here is the below code snippet in typescript for both BFS and DFS

class  NodeItem  {
	value:  number;
	left:  NodeItem  |  null;
	right:  NodeItem  |  null;

	constructor(value:  number)  {
		this.value = value;
		this.left =  null;
		this.right =  null;
		}
}

class  BinarySearchTree  {
	
	root:  NodeItem  |  null;		
	
	constructor()  {
		this.root =  null;
	}

insert(value:  number)  {
	let newNode =  new  NodeItem(value);
	
	if (this.root ===  null) {
	this.root = newNode;

	return  this;
}  else  {
	this.insertNode(this.root, newNode);
	}
}
 

private  insertNode(node:  NodeItem,  newNode:  NodeItem)  {
	if (newNode.value < node.value) {
		if (node.left ===  null) {
			node.left = newNode;
		}  else  {
			this.insertNode(node.left, newNode);
		}
	}  else  if (newNode.value > node.value) {
		if (node.right ===  null) {
			node.right = newNode;
		}  else  {
			this.insertNode(node.right, newNode);
		}
	}
}

contains(value:  number):  boolean  {
	if (this.root ===  null) return  false;
	let current:  NodeItem  |  null  =  this.root;
	let found:  Boolean  =  false;

	while (current &&  !found) {
		if (value < current.value) {
			current = current.left;
		}  else  if (value > current.value) {
			current = current.right;
		}  else  {
		return  true;
		}
}
	return  false;
}
bfs():  number[] {
	let data:  number[] = [];
	let queue: (NodeItem  |  null)[] = [];
	let current =  this.root;
	if (current !==  null) {
		queue.push(current);	
	}
	while (queue.length >  0) {
			current = queue.shift()!;
			data.push(current.value);
		if (current.left !==  null) {
			queue.push(current.left);
		}
		if (current.right !==  null) {
			queue.push(current.right);
		}
	}
return data;
}

  

dfsPreOrder():  number[] {
	let data:  number[] = [];
	if (this.root !=  null) {
		this.traversePreOrder(this.root, data);
	}
	return data;
}

dfsPostOrder():  number[] {
	let data:  number[] = [];
	if (this.root !=  null) {
		this.traversePostOrder(this.root, data);
	}
	return data;
}  

dfsInOrder():  number[] {
	let data:  number[] = [];
	
	if (this.root !=  null) {
		this.traverseInOrder(this.root, data);
	}
	return data;
}

  

private  traversePreOrder(node:NodeItem,data:number[]):void  {
		data.push(node.value);
		if (node.left !== null) this.traversePreOrder(node.left,data);
		if (node.right !==  null) this.traversePreOrder(node.right, data);
}


private traversePostOrder(node:  NodeItem,  data:  number[]):  void  {

 if (node.left !==  null) this.traversePostOrder(node.left, data); 
 if (node.right !==  null) this.traversePostOrder(node.right, data);
 data.push(node.value);
}

private traverseInOrder(node:  NodeItem,  data:  number[]):  void  {
 if (node.left !==  null) this.traverseInOrder(node.left, data);
 data.push(node.value);
 if (node.right !==  null) this.traverseInOrder(node.right, data);
}

}

  

let tree =  new BinarySearchTree();

tree.insert(10);
tree.insert(7);
tree.insert(2);
tree.insert(8);
tree.insert(12);
tree.insert(15);
 

console.log(tree.dfsPreOrder());
console.log(tree.dfsPostOrder());
console.log(tree.dfsInOrder());

Thank you !!