Data Structure and Algorithms

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

Coding Example:

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

    def insert_node(self, value):
        if value <= self.value and self.left_child:
            self.left_child.insert_node(value)
        elif value <= self.value:
            self.left_child = BinarySearchTree(value)
        elif value > self.value and self.right_child:
            self.right_child.insert_node(value)
        else:
            self.right_child = BinarySearchTree(value)

    def find_node(self, value):
        if value < self.value and self.left_child:
            return self.left_child.find_node(value)
        if value > self.value and self.right_child:
            return self.right_child.find_node(value)

        return value == self.value

    def remove_node(self, value, parent):
        if value < self.value and self.left_child:
            return self.left_child.remove_node(value, self)
        elif value < self.value:
            return False
        elif value > self.value and self.right_child:
            return self.right_child.remove_node(value, self)
        elif value > self.value:
            return False
        else:
            if self.left_child is None and self.right_child is None and self == parent.left_child:
                parent.left_child = None
                self.clear_node()
            elif self.left_child is None and self.right_child is None and self == parent.right_child:
                parent.right_child = None
                self.clear_node()
            elif self.left_child and self.right_child is None and self == parent.left_child:
                parent.left_child = self.left_child
                self.clear_node()
            elif self.left_child and self.right_child is None and self == parent.right_child:
                parent.right_child = self.left_child
                self.clear_node()
            elif self.right_child and self.left_child is None and self == parent.left_child:
                parent.left_child = self.right_child
                self.clear_node()
            elif self.right_child and self.left_child is None and self == parent.right_child:
                parent.right_child = self.right_child
                self.clear_node()
            else:
                self.value = self.right_child.find_minimum_value()
                self.right_child.remove_node(self.value, self)

            return True

    def clear_node(self):
        self.value = None
        self.left_child = None
        self.right_child = None

    def find_minimum_value(self):
        if self.left_child:
            return self.left_child.find_minimum_value()
        else:
            return self.value

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

• Google - DSA
• Illinois - DSA
• CrazyProgrammer - Trees
• Trees - FreeCodeCamp
• binary tree - WikiPedia
• binary search tree
• A* Example by The Coding Train, Jan 16,2017