Documentation

This module provides a Node class, node functions, and tree functions for a binary tree data structure.

Example

from binary_tree import from_string, from_orders, traverse

node = from_string("1,2,,3,4,,5")

in_order = list(traverse(node, "in"))
pre_order = list(traverse(node, "pre"))
node2 = from_orders("in-pre", in_order, pre_order)

>>> repr(node) == repr(node2)
True

Node

class binary_tree.Node(value, **nodes)

The basic unit of a binary tree structure.

value

The node value.

left

The left child Node instance, if present.

right

The right child Node instance, if present.

prev

The left neighbouring Node instance, if present.

next

The right neighbouring Node instance, if present.

parent

The parent Node instance, if present.

Comparing the value of a Node instance

Node.__eq__(other)

Tentatively compare the value of self and other.

If other does not have a value, use other itself as a basis of comparison.

Parameters:other – Any object. Returns:True if the value of self is equal to the value of other, or other itself- and False otherwise.

Getting the binary tree structure of a Node instance

Node.__repr__()

Get the full representation of self.

repr() comprises of value, the repr() of left if present, and the repr() of right if present.

Returns:A full representation of self. Return type:str

Iterating over the binary tree structure of a Node instance

Node.__iter__()

Traverse the binary tree structure of self in level-order.

Yields:A Node in the binary tree structure of self.

node

This module contains functions for the Node class.

Checking for a Node instance

binary_tree.node.is_node(obj)

Check if obj is an instance of Node.

Parameters:obj – Any object. Returns:True if obj is an instance of Node, False otherwise.

Checking for a child Node instance

binary_tree.node.is_left(node)

Check if node is a left child.

Returns:True if node is the left node of its parent, False otherwise, or if its parent is not set.

binary_tree.node.is_right(node)

Check if node is a right child.

Returns:True if node is the right node of its parent, False otherwise, or if its parent is not set.

Checking for a Node instance in a binary tree structure

binary_tree.node.is_leaf(node)

Check if node is a leaf node.

Returns:True if node has a parent but no left or right node, False otherwise.

binary_tree.node.is_root(node)

Check if node is a root node.

Returns:True if node has a left or right node but no parent node, False otherwise.

binary_tree.node.is_orphan(node)

Check if node is an orphan node.

Returns:True if node has no parent, left, and right node, False otherwise.

tree

This module contains functions for binary trees.

Constructing a Node instance with a binary tree structure

binary_tree.tree.from_string(tree_string, cls=<class 'binary_tree.node.Node'>)

Construct a Node instance with the binary tree structure represented by tree_string.

Initializes the root Node instance (the first level), followed by left and then right for every Node instance per level (level-order).

Parameters:

• tree_string (str) – A level-order binary tree traversal, separated by commas.
• cls (type) – The class constructor to use. Defaults to 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.

binary_tree.tree.from_orders(kind, in_order, other_order, cls=<class 'binary_tree.node.Node'>)

Construct a Node instance with the binary tree structure that entails in-order and other_order.

Recursively initializes parent, left, and then right. (pre-order).

Parameters:

• 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 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.

binary_tree.tree.connect_nodes(root)

Connect the Node instances in each level of root.

Parameters:root – A root Node instance.

binary_tree.tree.to_string(root)

Deconstruct root into a string.

Parameters:root – A root Node instance. Returns:A level-order binary tree traversal, separated by commas. Return type:str

Note

Empty spaces in the tree string are indicated with "null".

Traversing a Node instance with a binary tree structure

binary_tree.tree.traverse_pre_order(root)

Traverse root in pre-order.

Visit parent, left, and then right.

Parameters:root – A root Node instance. Yields:A Node instance in the binary tree structure of root.

binary_tree.tree.traverse_in_order(root)

Traverse root in in-order.

Visit left, parent, and then right.

Parameters:root – A root Node instance. Yields:A Node instance in the binary tree structure of root.

binary_tree.tree.traverse_post_order(root)

Traverse root in post-order.

Visit left, right, and then parent.

Parameters:root – A root Node instance. Yields:A Node instance in the binary tree structure of root.

binary_tree.tree.traverse_level_order(root)

Traverse root in level-order.

Visit root (the first level), followed by left and then right for every Node instance per level.

Parameters:root – A root Node instance. Yields:A list of Node instances representing a level in root.

binary_tree.tree.traverse(root, kind)

Forward root to the kind of traversal.

Parameters:

• root – A root 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.

Analyzing a Node instance with a binary tree structure

binary_tree.tree.is_symmetrical(root)

Check for symmetry in root.

Parameters:root – A root Node instance. Returns:True if the binary tree structure of root is symmetrical, False otherwise.

binary_tree.tree.max_depth(root)

Calculate the maximum depth of root.

Parameters:root – A root Node instance. Returns:The total number of levels in the binary tree structure of root. Return type:int

binary_tree.tree.get_path(node)

Trace the ancestry of node.

Parameters:node – A Node instance in a binary tree. Returns:A list of Node instances from the greatest ancestor to node.

binary_tree.tree.all_paths(root)

Find every leaf path in root.

Search for leaf nodes in root using post-order traversal.

Parameters:root – A root Node instance. Yields:A list of Node instances from root to a leaf Node instance.

binary_tree.tree.has_sum(root, value)

Determine if there is a path in root that adds up to value.

Parameters:

• root – A root Node instance.
• value – The sum to check for.

Returns:

True if a path that adds up to value exists in root, False otherwise.

binary_tree.tree.find_path(root, node)

Find the path of (the Node instance of) node in root.

Parameters:

• root – A root Node instance.
• node – A Node instance or value in root.

Returns:

A list of every Node instance from root to (the 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.

binary_tree.tree.get_lca(root, *nodes)

Get the lowest common ancestor of two or more (Node instances of) nodes in root.

Parameters:

• root – A root Node instance.
• *nodes (Node) – Node instances or values in root.

Returns:

The Node instance that is the lowest common ancestor of (the 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.