Practice Binary Trees and Searching
Master binary tree structures and efficient searching algorithms to solve complex coding 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 {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Binary Search Tree implementation
class BinarySearchTree {
Node root;
public BinarySearchTree() {
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
public Node search(int value) {
return searchNode(this.root, value);
}
private Node searchNode(Node node, int 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 searchNode(node.left, value); } else { return searchNode(node.right, value); }
}
BST Insert Implementation:
// Insert a value into BST
public void insert(int value) {
Node newNode = new Node(value);
if (this.root == null) {
this.root = newNode;
return;
}
insertNode(this.root, newNode);
}
private void insertNode(Node node, 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 { insertNode(node.left,
newNode); } } else { // If value is greater than node's value, go right if (node.right==null) {
node.right=newNode; } else { 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
public int linearSearch(int[] arr, int target) {
for (int 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)
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) { int mid=left + (right - left) / 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; } else { // If target is smaller, ignore right half right=mid - 1; } } // Target not
found return -1; } // Time Complexity: O(log n) // Space Complexity: O(1)
Recursive Binary Search
// Binary Search implementation (recursive)
public int binarySearchRecursive(int[] arr, int target, int left, int right) {
// Base case: element not found
if (left > right) {
return -1;
}
int mid = left + (right - left) / 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.