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:
        def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

        # Binary Search Tree implementation
        class BinarySearchTree:
        def __init__(self):
        self.root = None

        # 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
        def search(self, value):
        return self._searchNode(self.root, value)

        def _searchNode(self, node, value):
        # Base cases: empty tree or found the value
        if node is None:
        return None
        if node.value == value:
        return node

        # Recursive cases
        if value < node.value: return self._searchNode(node.left, value) else: return self._searchNode(node.right,
          value) 

BST Insert Implementation:

            # Insert a value into BST
            def insert(self, value):
            newNode = Node(value)
            if self.root is None:
            self.root = newNode
            return self
            self._insertNode(self.root, newNode)
            return self

            def _insertNode(self, node, newNode):
            # If value is less than node's value, go left
            if newNode.value < node.value: if node.left is None: node.left=newNode else: self._insertNode(node.left,
              newNode) # If value is greater than node's value, go right else: if node.right is None: node.right=newNode
              else: self._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
              def linear_search(arr, target):
              for i in range(len(arr)):
              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)
              def binary_search(arr, target):
              left = 0
              right = len(arr) - 1
              while left <= right: mid=(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)
                  def binary_search_recursive(arr, target, left=0, right=None):
                  if right is None:
                  right = len(arr) - 1
                  # Base case: element not found
                  if left > right:
                  return -1
                  mid = (left + right) // 2
                  # Found the target
                  if arr[mid] == target:
                  return mid
                  # Recursive cases
                  if arr[mid] > target:
                  return binary_search_recursive(arr, target, left, mid - 1)
                  else:
                  return binary_search_recursive(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.