# Stacks

A **stack** is a data structure used to store a collection of objects or elements **where the addition of new items and the removal of existing items always take place at the top of the stack**.

class Stack(object): def __init__(self): self.items = [] def __len__(self): # It returns the number of elements in the stack. return len(self.items) def push(self, item): # It adds a new item to the top of the stack. self.items.append(item)

*The top of the stack is the last element in our list.* However, the intricacies of our implementation are totally hidden from the user.

def pop(self): # It removes the top element from the stack and returns the removed item. if not self.is_empty(): return self.items.pop() # The Python's pop() method takes a single argument (index). If an argument is not passed to the function, it uses the default index -1. def peek(self): # It returns the top element from the stack but does not remove it. if not self.is_empty(): return self.items[-1] def is_empty(self): # It returns true when the stack is empty, otherwise, the function returns false. return len(self.items) == 0 def __str__(self): # It allows us to print our stack. s = "{ " for i in range(len(self.items)): if i != len(self.items)-1: s += str(self.items[i]) + ", " else: s += str(self.items[i]) + " }" return s @classmethod def createRandomStack(cls, n): myStack = Stack() for i in range(n): i = random.randint(0, 100) myStack.push(i) return myStack def main(): myStack = Stack.createRandomStack(10) print(myStack) # { 58, 8, 91, 52, 98, 30, 41, 4, 32, 37 } print(len(myStack)) # 10 print(myStack.pop()) # 37 print(myStack) # { 58, 8, 91, 52, 98, 30, 41, 4, 32 } if __name__ == '__main__': main()

# Queues

A **queue** is a data structure used to store a collection of objects or elements which works exactly like how a real-life queue works, that is, a FIFO data structure in which **the element that is inserted first into the queue is the first one to be taken out**. It models or enforces a first-come first-serve policy.

class Queue(): def __init__(self): self.items = [] def __len__(self): # It returns the number of elements in the queue. return len(self.items) def enqueue(self, item): # It adds a new item to the tail of the queue.The tail of the queue is the first element in our list.self.items.insert(0, item) def dequeue(self): # It removes the first element from the queue (the element at the head of the queue) and returns the removed item. if not self.is_empty(): return self.items.pop() def is_empty(self): # It returns true when the queue is empty, otherwise, the function returns false. return len(self.items) == 0 def peek(self): # It returns the first element from the queue but does not remove it. if not self.is_empty(): return self.items[-1] def __str__(self): # It allows us to print our queue. s = "{ " for i in range(len(self.items)): if i != len(self.items)-1: s += str(self.items[i]) + ", " else: s += str(self.items[i]) + " }" return s @classmethod def createRandomQueue(cls, n): myQueue = Queue() for i in range(n): i = random.randint(0, 100) myQueue.enqueue(i) return myQueue def main(): myQueue = Queue.createRandomQueue(10) print(myQueue) # { 76, 2, 15, 58, 60, 1, 30, 77, 35, 7 } print(len(myQueue)) # 10 print(myQueue.dequeue()) # 7 print(myQueue) # { 76, 2, 15, 58, 60, 1, 30, 77, 35 } if __name__ == '__main__': main()

# Binary Trees

A **tree** is a nonlinear data structure that's quite often used to represent hierarchical data. A tree has a value and children, and its children are themselves trees. It is more technically defined as a graph where there is at most one path from any node to any other node.

A **binary tree** is a tree data structure used to store a collection of objects or elements **in which each node has at most two children, which are referred to as the left and the right child**.

A **binary search tree** is a binary tree in which, at any node, **all the nodes in the left subtree have a lesser value than the node, and all nodes in the right subtree have a greater value than the node**. It quickly allows us to maintain a sorted list of numbers.

class BinaryTree: def __init__(self, value): self.data = value self.left = None self.right = None

*one way to traverse through the tree data*.

def preorder(self): """In a preorder traversal, the root node is visited first, followed by the left tree, then the right tree. [8, 3, 1, 6, 4, 7, 10, 14, 13]""" result = [] result.append(self.data) if self.left is not None: result += self.left.preorder() if self.right is not None: result += self.right.preorder() return result def inorder(self): """In an inorder traversal, the left tree is visited first, followed by the root node, then followed by the right tree.""" result = [] if self.left is not None: result += self.left.inorder() result.append(self.data) if self.right is not None: result += self.right.inorder() return result

The inorder traversal produces the sorted list (more technically, the sorted sequence of keys), e.g. [1, 3, 4, 6, 7, 8, 10, 13, 14]

def postorder(self): """In a postorder traversal, the left tree is visited first, followed by the right tree, then the root node. [1, 4, 7, 6, 3, 13, 14, 10, 8]""" result = [] if self.left is not None: result += self.left.postorder() if self.right is not None: result += self.right.postorder() result.append(self.data) return result

A **level order traversal**, i.e. **traverse the tree level-by-level, is implemented using a queue**. We need to visit the root node first and then visit its child nodes, then their child nodes, etc. First, we push the root inside the queue. Then, we loop till the queue is empty, popping out the first node in the queue and pushing its child nodes inside the queue, e.g. [8, 3, 10, 1, 6, 14, 4, 7, 13]

def level(self): queue = Queue() queue.enqueue(self) result = [] while len(queue) > 0: result.append(queue.peek().data) myNode = queue.dequeue() if myNode.left is not None: queue.enqueue(myNode.left) if myNode.right is not None: queue.enqueue(myNode.right) return result def __str__(self): return str(self.level())

Displaying all the nodes in reverse level order is quite similar to a level order traversal, but we use a stack, too. First, we push the root inside the queue. Then, we loop till the queue is empty, popping out the first node in the queue, pushing it into the stack (observe that we use a stack to keep top-level nodes at the bottom of the stack), then pushing its right child first and then its left child into the queue, e.g. [4, 7, 13, 1, 6, 14, 3, 10, 8].

def reverse_level(self): queue = Queue() stack = Stack() queue.enqueue(self) result = [] while len(queue) > 0: myNode = queue.dequeue() stack.push(myNode) if myNode.right is not None: queue.enqueue(myNode.right) if myNode.left is not None: queue.enqueue(myNode.left) while len(stack) > 0: node = stack.pop() result.append(node.data) return result def is_leaf(self): # It returns True if the node does not have any child nodes and returns False otherwise return (self.left is None) and (self.right is None) def add_child(self, value): # When looking for a place to insert a new "value", we need to traverse the tree from root to leaf, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees. if value == self.data: return if value < self.data: if self.left is not None: # We need to continue searching in the left subtree. self.left.add_child(value) else: # If value is smaller than the current node's data and the current node does not have any left child, then we have found its place. self.left = BinaryTree(value) else: if self.right is not None: self.right.add_child(value) else: self.right = BinaryTree(value) @classmethod def build_tree(cls, values): # It builds a tree from a list representation myTree = BinaryTree(values[0]) for i in range(1, len(values)): myTree.add_child(values[i]) return myTree def print_tree(self, traversal_type): if traversal_type == "preorder": return self.preorder() elif traversal_type == "inorder": return self.inorder() elif traversal_type == "postorder": return self.postorder() elif traversal_type == "level": return self.level() elif traversal_type == "reverse_level": return self.reverse_level() else: print("Traversal type " + str(traversal_type) + " not recognized.") return False def height(self): #The height of a binary tree is the maximum depth of the tree, that is, the distance from the root node to its furthest leaf. if self is None: return 0 if self.is_leaf(): return 1 else: leftHeight, rightHeight = 0, 0 if self.left is not None: leftHeight = self.left.height() if self.right is not None: rightHeight = self.right.height() return 1 + max(leftHeight, rightHeight) def size(self): # The size of a binary tree is the number of nodes in it. if self is None: return 0 if self.is_leaf(): return 1 leftSize, rightSize = 0, 0 if self.left is not None: leftSize = self.left.size() if self.right is not None: rightSize = self.right.size() return 1 + leftSize + rightSize def find(self, value): """To find value, we need to traverse the tree from root to leaf, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees. If the value at the current node is less than the search target, then we need to search to the right, so we recursively proceed down the right subtree, else if it’s greater than the search target, then we will need to go down the left subtree.""" if self is None: return False if self.data == value: return True elif (value < self.data and self.left is not None): return self.left.find(value) elif (value > self.data and self.right is not None): return self.right.find(value) else: return False def delete(self, value): """First, we should proceed the same as before, we need to traverse the tree, making comparisons to the values of the tree's nodes and deciding based on these comparisons to continue searching in the left or right subtrees.""" if value < self.data: if self.left is not None: self.left = self.left.delete(value) elif value > self.data: if self.right is not None: self.right = self.right.delete(value) else: # We have already found it! if self.is_leaf(): # If the node is a leaf node, we just return None. return None elif self.left is None: # If the node does have one single child, say the right child, we return it. In other words, its child takes its position. return self.right elif self.right is None: return self.left # This is the tricky part, the node has two children. We need to find the minimum value in its right subtree (1), copy its value (2), and remove the duplicate (3). min_value = self.right.find_min() # (1) self.data = min_value # (2) self.right = self.right.delete(min_value) # (3) return self

def find_min(self): if self.left is None: return self.data return self.left.find_min() def main(): tree = BinaryTree.build_tree([8, 3, 10, 1, 6, 14, 4, 7, 13]) print(tree.print_tree("level")) # [8, 3, 10, 1, 6, 14, 4, 7, 13] print(tree.print_tree("preorder")) # [8, 3, 1, 6, 4, 7, 10, 14, 13] print(tree.print_tree("inorder")) # [1, 3, 4, 6, 7, 8, 10, 13, 14] print(tree.print_tree("postorder")) # [1, 4, 7, 6, 3, 13, 14, 10, 8] print(tree.print_tree("reverse_level")) # [4, 7, 13, 1, 6, 14, 3, 10, 8] print(tree.height()) # 4 print(tree.size()) # 9 print(tree.find(6)) # True print(tree.find(13)) # True print(tree.find(2)) # False print(tree.find_min()) # 1 print(tree.is_leaf()) # False tree.delete(7) tree.delete(3) print(tree) # [8, 4, 10, 1, 6, 14, 13] if __name__ == '__main__': main()

A **balanced binary tree** is defined as a binary tree in which *the left and right subtrees of every node differ in height by no more than 1*.

def is_balanced(self): if self is None: return True if self.is_leaf(): return True if self.right is None: return self.left.height() <= 1 if self.left is None: return self.right.height() <= 1 return self.right.is_balanced() and self.left.is_balanced() and abs(self.left.height() - self.right.height()) <= 1 def main(): tree = BinaryTree.build_tree([8, 3, 10, 1, 6, 14, 4, 7, 13]) # [8, 3, 10, 1, 6, 14, 4, 7, 13] print(tree.is_balanced()) # False tree.add_child(9) # [8, 3, 10, 1, 6, 9, 14, 4, 7, 13] print(tree.is_balanced()) # True if __name__ == '__main__': main()

An "

**AVL tree is a self-balancing Binary Search Tree**(BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes," GeeksforGeeks, AVL Tree | Set 1 (Insertion). Compártelo / Share it!