Practice Binary Trees and Searching

Master binary tree structures and efficient searching algorithms to solve complex coding problems.

Module Objectives

Binary Trees

Upon completion of the binary trees module, you will be able to:

Understand the layout and structure of a binary tree
Distinguish between a binary tree and a binary search tree (BST)
Analyze the time complexity of searching and inserting into a binary search tree
Implement a binary search tree with basic operations

Searching Algorithms

Upon completion of the searching module, you will be able to:

Implement a linear search algorithm
Implement a binary search algorithm
Understand the time complexity differences between linear and binary search
Apply these searching algorithms to solve practical problems

Binary Tree Basics

A binary tree is a hierarchical data structure where each node has at most two children, referred to as left and right child nodes.

Key Terminology:

Root: The topmost node of the tree
Parent/Child: Relationship between connected nodes
Leaf: A node with no children
Height: The length of the longest path from root to leaf
Depth: The length of the path from root to a specific node

// Binary Tree Node
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Binary Search Tree implementation
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // Other methods will be implemented below
}
      

Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree where:

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 are also BSTs

BST Search Implementation:

// Search for a value in BST
search(value) {
  return this._searchNode(this.root, value);
}

_searchNode(node, value) {
  // Base cases: empty tree or found the value
  if (node === null) return null;
  if (node.value === value) return node;
  
  // Recursive cases
  if (value < node.value) {
    return this._searchNode(node.left, value);
  } else {
    return this._searchNode(node.right, value);
  }
}
      

BST Insert Implementation:

// Insert a value into BST
insert(value) {
  const newNode = new Node(value);
  
  if (this.root === null) {
    this.root = newNode;
    return this;
  }
  
  this._insertNode(this.root, newNode);
  return this;
}

_insertNode(node, newNode) {
  // If value is less than node's value, go left
  if (newNode.value < node.value) {
    if (node.left === null) {
      node.left = newNode;
    } else {
      this._insertNode(node.left, newNode);
    }
  } 
  // If value is greater than node's value, go right
  else {
    if (node.right === null) {
      node.right = newNode;
    } else {
      this._insertNode(node.right, newNode);
    }
  }
}
      

Searching Algorithms

Linear Search

Linear search is the simplest searching algorithm that checks each element of the array one by one until the target is found or the array is exhausted.

// Linear Search implementation
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Return index if found
    }
  }
  return -1; // Return -1 if not found
}

// Time Complexity: O(n)
// Space Complexity: O(1)
      

Binary Search

Binary search is a divide-and-conquer algorithm that works on sorted arrays by repeatedly dividing the search interval in half.

// Binary Search implementation (iterative)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    // Check if target is at mid
    if (arr[mid] === target) {
      return mid;
    }
    
    // If target is greater, ignore left half
    if (arr[mid] < target) {
      left = mid + 1;
    } 
    // If target is smaller, ignore right half
    else {
      right = mid - 1;
    }
  }
  
  // Target not found
  return -1;
}

// Time Complexity: O(log n)
// Space Complexity: O(1)
      

Recursive Binary Search

// Binary Search implementation (recursive)
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // Base case: element not found
  if (left > right) {
    return -1;
  }
  
  const mid = Math.floor((left + right) / 2);
  
  // Found the target
  if (arr[mid] === target) {
    return mid;
  }
  
  // Recursive cases
  if (arr[mid] > target) {
    return binarySearchRecursive(arr, target, left, mid - 1);
  } else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}
      

Practice Exercises

Now it's time to practice what you learned!

You should have already created your Code Signal account. If you have not done so yet, please follow these instructions What is CodeSignal and How to Create Your Account.

Tip: Before you dive into the practice tasks, revisit the core competency and guided project videos in this sprint.

Complete these tasks in CodeSignal:

ACS2M4

ACS2M5

ACS2M6

Bonus - Once you have finished the above tasks, here is an extra challenge!

Login to CodeSignal
Click on the task links above
Select your preferred language
Click on NEXT to begin
Agree with the Terms and Pledges and click START

Once all the questions for each task are completed in Code Signal, click on Finish the Test.