Skip to content

Data Structure and Algorithms

Jump to bottom
Heath Brown edited this page Dec 23, 2023 · 21 revisions

Data Structures

Linear

Arrays

Hash Tables

Linked Lists

Stacks

Queues

Non-Linear

Trees

  • Trees are collection of Nodes
  • Nodes are connected via Edges
  • Nodes contain data or a value
  • Nodes may or may not have children

FreeCodeCamp terminology summary

  • Root is the topmost node of the tree
  • Edge is the link between two nodes
  • Child is a node that has a parent node
  • Parent is a node that has an edge to a child node
  • Leaf is a node that does not have a child node in the tree
  • Height is the length of the longest path to a leaf
  • Depth is the length of the path to its root

Binary Trees

  • Each node has at most two children
  • left_child
  • right_child
  • and contains a value

Code example:

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def insert_left(self, value):
        if self.left_child == None:
            self.left_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.left_child = self.left_child
            self.left_child = new_node

    def insert_right(self, value):
        if self.right_child == None:
            self.right_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.right_child = self.right_child
            self.right_child = new_node

Tree Traversal

  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
Binary Search Tree
  • ordered or sorted binary trees
  • keeps values sorted order
  • Binary Search Node is larger than value of the offspring of its left child
  • Binary Search Node is smaller than value of the offspring of its right child

Graphs

Algorithms

Depth-First Search (DFS)

  • used in tree traversal
  • requires going down to each leaf node before backtracking

DFS Types

  • pre-order 
      def pre_order(self):
      print(self.value)

      if self.left_child:
          self.left_child.pre_order()

      if self.right_child:
          self.right_child.pre_order()
  • in-order 
      def in_order(self):
      if self.left_child:
          self.left_child.in_order()

      print(self.value)

      if self.right_child:
          self.right_child.in_order()
  • post-order 
      def post_order(self):
      if self.left_child:
          self.left_child.post_order()

      if self.right_child:
          self.right_child.post_order()

      print(self.value)

Breadth-First Search (BFS)

  • Used in tree traversal
  • traverses the tree level by level and depth by depth

Code:

def bfs(self):
    queue = Queue()
    queue.put(self)

    while not queue.empty():
        current_node = queue.get()
        print(current_node.value)

        if current_node.left_child:
            queue.put(current_node.left_child)

        if current_node.right_child:
            queue.put(current_node.right_child)

Resources

Clone this wiki locally