binary_search_tree.py

import time


class BinarySearchTree:
    """
    Binary Search Tree node.
    Each node holds data and links to left/right children.
    Left child < current node < Right child
    """

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

    def insert(self, data):
        """Insert data — duplicates are ignored."""
        if data == self.data:
            return
        if data < self.data:
            if self.left:
                self.left.insert(data)
            else:
                self.left = BinarySearchTree(data)
        else:
            if self.right:
                self.right.insert(data)
            else:
                self.right = BinarySearchTree(data)

    def search(self, val, comparisons=0):
        """
        Search for val. Returns (found: bool, comparisons: int).
        BUG FIX: original code checked `result == None` but search
        returned True/False, so not-found always returned (1, t) wrongly.
        """
        comparisons += 1
        if self.data == val:
            return True, comparisons
        if val < self.data:
            if self.left:
                return self.left.search(val, comparisons)
            return False, comparisons
        if self.right:
            return self.right.search(val, comparisons)
        return False, comparisons

    def in_order(self):
        elements = []
        if self.left:
            elements += self.left.in_order()
        elements.append(self.data)
        if self.right:
            elements += self.right.in_order()
        return elements

    def pre_order(self):
        elements = [self.data]
        if self.left:
            elements += self.left.pre_order()
        if self.right:
            elements += self.right.pre_order()
        return elements

    def post_order(self):
        elements = []
        if self.left:
            elements += self.left.post_order()
        if self.right:
            elements += self.right.post_order()
        elements.append(self.data)
        return elements

    def find_max(self):
        if self.right is None:
            return self.data
        return self.right.find_max()

    def find_min(self):
        if self.left is None:
            return self.data
        return self.left.find_min()

    def node_sum(self):
        left_sum = self.left.node_sum() if self.left else 0
        right_sum = self.right.node_sum() if self.right else 0
        return self.data + left_sum + right_sum


def build_tree_and_search(elements, target):
    """
    Build a BST from elements list, then search for target.
    Returns (found: bool, elapsed_seconds: float, comparisons: int)
    """
    if not elements:
        return False, 0.0, 0

    root = BinarySearchTree(elements[0])
    for item in elements[1:]:
        root.insert(item)

    t_start = time.perf_counter()
    found, comparisons = root.search(target)
    t_stop = time.perf_counter()

    elapsed = t_stop - t_start
    return found, elapsed, comparisons