Trees

Trees

This directory contains Python implementations of various tree-based data structures and algorithms.

Contents

Binary Search Trees (BST)

• Binary Search Tree Implementation: A comprehensive implementation of a BST with TreeNode and BinarySearchTree classes, including insertion, deletion, and search.
• Validate BST (Solution 1): Validates a BST by performing an in-order traversal and checking if the resulting values are sorted.
• Validate BST (Solution 2): Validates a BST by keeping track of the minimum and maximum allowable values for each node.
• Trim a BST: Trims a BST so that all node values fall within a specified range $[min, max]$.

Search Algorithms

• Binary Search (Iterative): Iterative implementation of the binary search algorithm on a sorted list.
• Binary Search (Recursive): Recursive implementation of the binary search algorithm.

Heaps

• Binary Heap Implementation: Implements a min-heap using a recursive approach, including insert, delMin, and buildHeap.

Tree Representations & Traversals

• Nodes and References Representation: A simple implementation of a binary tree using a class-based nodes and references approach.
• List of Lists Representation: Demonstrates building and manipulating a tree using a "list of lists" approach.
• Tree Level Order Print: Prints a binary tree in level order (breadth-first) using a queue, with each level on a new line.