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)[source]¶

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)[source]¶

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__()[source]¶

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__()[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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'>)[source]¶

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'>)[source]¶

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)[source]¶

Connect the Node instances in each level of root.

Parameters:	root – A root `Node` instance.

binary_tree.tree.to_string(root)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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.