Source code for binary_tree.tree

# -*- coding: utf-8 -*-

"""This module contains functions for binary trees."""

from .node import Node, is_node, is_leaf
import functools

[docs]def connect_nodes(root): """Connect the :class:`~binary_tree.Node` instances in each level of `root`. Args: root: A root :class:`~binary_tree.Node` instance. """ for level in traverse_level_order(root): prev_node, next_node = None, None for i in range(len(level)): prev_node, level[i].prev, next_node, level[-i-1].next = ( level[i], prev_node, level[-i-1], next_node)
[docs]def from_string(tree_string, cls=Node): """Construct a :class:`~binary_tree.Node` instance with the binary tree structure represented by `tree_string`. Initializes the root :class:`~binary_tree.Node` instance (the first level), followed by :attr:`~binary_tree.Node.left` and then :attr:`~binary_tree.Node.right` for every :class:`~binary_tree.Node` instance per level (level-order). Args: tree_string (str): A level-order binary tree traversal, separated by commas. cls (type): The class constructor to use. Defaults to :class:`~binary_tree.Node`. Returns: A newly initialized `cls` instance with the binary tree structure that represents `tree_string`. If `tree_string` has no root value, returns ``None``. Note: Empty spaces can be represented by an immediate comma or ``"null"`` for explicitness. """ for char in " []\n'\"": tree_string = tree_string.replace(char, "") values = iter(tree_string.split(",")) value = next(values) if value == "": # Empty root value. return None try: value = int(value) except ValueError: # value is not a number. pass root = cls(value) level = [root] while level: next_level = [] for node in level: for side in ["left", "right"]: try: value = next(values) except StopIteration: # values has been exhausted. break # break out of all loops if value in ["", "null"]: # Not a node. continue try: value = int(value) except ValueError: # value is not a number. pass child = cls(value) setattr(node, side, child) next_level.append(child) else: continue break else: level = next_level continue break connect_nodes(root) return root
[docs]def from_orders(kind, in_order, other_order, cls=Node): """Construct a :class:`~binary_tree.Node` instance with the binary tree structure that entails `in-order` and `other_order`. Recursively initializes :attr:`~binary_tree.Node.parent`, :attr:`~binary_tree.Node.left`, and then :attr:`~binary_tree.Node.right`. (pre-order). Args: kind (str): Either "in-pre" or "in-post". in_order (list[int, ...]): The in-order traversal of a binary tree. other_order (list[int, ...]): Either the tree's pre-order or post-order traversal. cls (type): The class constructor to use. Defaults to :class:`~binary_tree.Node`. Returns: A newly initialized `cls` instance with the binary tree structure that entails `in_order` and `other_order`. If either arguments are empty, returns ``None``. Raises: ValueError: If `in_order` and `other_order` do not correspond to a binary tree structure or contain duplicates. KeyError: If `kind` is not one of the accepted keys. Note: There cannot be any duplicates in `in_order` and `other_order`. """ if kind == "in-pre": def make_node(in_order, other_order): if not in_order or not other_order: return None node = cls(other_order[0]) in_slice = in_order[:in_order.index(other_order[0])] other_slice = other_order[1:len(in_slice)+1] node.left = make_node(in_slice, other_slice) in_slice = in_order[in_order.index(other_order[0])+1:] other_slice = other_order[-len(in_slice):] node.right = make_node(in_slice, other_slice) return node elif kind == "in-post": def make_node(in_order, other_order): if not in_order or not other_order: return None node = cls(other_order[-1]) in_slice = in_order[:in_order.index(other_order[-1])] other_slice = other_order[:len(in_slice)] node.left = make_node(in_slice, other_slice) in_slice = in_order[in_order.index(other_order[-1])+1:] other_slice = other_order[-len(in_slice)-1:-1] node.right = make_node(in_slice, other_slice) return node else: raise KeyError("Invalid argument for kind. " "Expected \"in-pre\" or \"in-post\"") root = make_node(in_order, other_order) connect_nodes(root) return root
[docs]def to_string(root): """Deconstruct `root` into a string. Args: root: A root :class:`~binary_tree.Node` instance. Returns: str: A level-order binary tree traversal, separated by commas. Note: Empty spaces in the tree string are indicated with ``"null"``. """ tree_values = [] level = [root] while any(level): level_values = [] next_level = [] for node in level: level_values.append(getattr(node, "value", None)) for side in ["left", "right"]: next_level.append(getattr(node, side, None)) for value in level_values: if value: tree_values.append(str(value)) else: tree_values.append("null") level = next_level else: return ",".join(tree_values)
[docs]def traverse_pre_order(root): """Traverse `root` in pre-order. Visit :attr:`~binary_tree.Node.parent`, :attr:`~binary_tree.Node.left`, and then :attr:`~binary_tree.Node.right`. Args: root: A root :class:`~binary_tree.Node` instance. Yields: A :class:`~binary_tree.Node` instance in the binary tree structure of `root`. """ queue = [root] while queue: node = queue.pop() if is_node(node): yield node if is_node(node.right): queue.append(node.right) if is_node(node.left): queue.append(node.left)
[docs]def traverse_in_order(root): """Traverse `root` in in-order. Visit :attr:`~binary_tree.Node.left`, :attr:`~binary_tree.Node.parent`, and then :attr:`~binary_tree.Node.right`. Args: root: A root :class:`~binary_tree.Node` instance. Yields: A :class:`~binary_tree.Node` instance in the binary tree structure of `root`. """ queue = [root] while True: while is_node(queue[-1].left): queue.append(queue[-1].left) while queue: node = queue.pop() if is_node(node): yield node if is_node(node.right): queue.append(node.right) break else: return
[docs]def traverse_post_order(root): """Traverse `root` in post-order. Visit :attr:`~binary_tree.Node.left`, :attr:`~binary_tree.Node.right`, and then :attr:`~binary_tree.Node.parent`. Args: root: A root :class:`~binary_tree.Node` instance. Yields: A :class:`~binary_tree.Node` instance in the binary tree structure of `root`. """ queue = [root] visited = [] while True: while is_node(queue[-1].left): queue.append(queue[-1].left) while queue: node = queue[-1] if is_node(node.right) and node not in visited: visited.append(node) queue.append(node.right) break yield node queue.pop() else: return
[docs]def traverse_level_order(root): """Traverse `root` in level-order. Visit `root` (the first level), followed by :attr:`~binary_tree.Node.left` and then :attr:`~binary_tree.Node.right` for every :class:`~binary_tree.Node` instance per level. Args: root: A root :class:`~binary_tree.Node` instance. Yields: A list of :class:`~binary_tree.Node` instances representing a level in `root`. """ level = [root] while level: yield list(level) next_level = [] for node in level: for side in ["left", "right"]: child = getattr(node, side) if is_node(child): next_level.append(child) level = next_level
[docs]def traverse(root, kind): """Forward `root` to the `kind` of traversal. Args: root: A root :class:`~binary_tree.Node` instance. kind (str): "pre" or "in" or "post" or "level". Returns: The generator iterator of the `kind` of traversal (with `root` passed to it). Raises: KeyError: If `kind` is not one of the possible options. """ traversal = globals()["traverse_{kind}_order".format(kind=kind)] return traversal(root)
[docs]def is_symmetrical(root): """Check for symmetry in `root`. Args: root: A root :class:`~binary_tree.Node` instance. Returns: ``True`` if the binary tree structure of `root` is symmetrical, ``False`` otherwise. """ level = [root] while any(level): values = [] next_level = [] for node in level: values.append(getattr(node, "value", None)) for side in ["left", "right"]: next_level.append(getattr(node, side, None)) for i in range(len(values)): if values[i] != values[-i-1]: return False level = next_level else: return True
[docs]def max_depth(root): """Calculate the maximum depth of `root`. Args: root: A root :class:`~binary_tree.Node` instance. Returns: int: The total number of levels in the binary tree structure of `root`. """ return sum(1 for level in traverse_level_order(root))
[docs]def get_path(node): """Trace the ancestry of `node`. Args: node: A :class:`~binary_tree.Node` instance in a binary tree. Returns: A list of :class:`~binary_tree.Node` instances from the greatest ancestor to `node`. """ path = [node] parent = node.parent while parent: path.append(parent) parent = parent.parent path.reverse() return path
[docs]def all_paths(root): """Find every leaf path in `root`. Search for leaf nodes in `root` using post-order traversal. Args: root: A root :class:`~binary_tree.Node` instance. Yields: A list of :class:`~binary_tree.Node` instances from `root` to a leaf :class:`~binary_tree.Node` instance. """ for node in traverse_post_order(root): if is_leaf(node): yield get_path(node)
[docs]def has_sum(root, value): """Determine if there is a path in `root` that adds up to `value`. Args: root: A root :class:`~binary_tree.Node` instance. value: The sum to check for. Returns: ``True`` if a path that adds up to `value` exists in `root`, ``False`` otherwise. """ for path in all_paths(root): total = None for node in path: if total is None: total = node.value else: total += node.value if total == value: return True else: return False
[docs]def find_path(root, node): """Find the path of (the :class:`~binary_tree.Node` instance of) `node` in `root`. Args: root: A root :class:`~binary_tree.Node` instance. node: A :class:`~binary_tree.Node` instance or value in `root`. Returns: A list of every :class:`~binary_tree.Node` instance from `root` to (the :class:`~binary_tree.Node` instance of) `node`, or ``None`` if `node` is absent in `root`. Note: If `node` is a value, it must be unique within the binary tree structure of `root`. """ for root_node in traverse_post_order(root): if node == root_node: return get_path(root_node)
[docs]def get_lca(root, *nodes): """Get the lowest common ancestor of two or more (:class:`~binary_tree.Node` instances of) `nodes` in `root`. Args: root: A root :class:`~binary_tree.Node` instance. *nodes (Node): :class:`~binary_tree.Node` instances or values in `root`. Returns: The :class:`~binary_tree.Node` instance that is the lowest common ancestor of (the :class:`~binary_tree.Node` instances of) `nodes` in `root`, or ``None`` if there is no common ancestor. Note: Values in `nodes` must be unique within the binary tree structure of `root`. """ if len(nodes) < 2: return None paths = [] lca_index = None for node in nodes: path = find_path(root, node) paths.append(path) max_index = len(path) - 1 if lca_index is None or max_index < lca_index: lca_index = max_index ref_path = paths.pop() for path in paths: while path[lca_index] is not ref_path[lca_index]: lca_index -= 1 return ref_path[lca_index]