Traversal

This module provides some common tree traversal algorithms that visit all the nodes in a tree data structure in a specific order.

trees.binary_trees.traversal.Pairs

An iterator of Key-Value pairs. Yield by traversal functions.

alias of Iterator[Tuple[Any, Any]]

trees.binary_trees.traversal.SupportedNodeType

Alias for the supported node types.

alias of None | Node | AVLNode

trees.binary_trees.traversal.SupportedTreeType

Alias for the supported types of binary trees.

alias of AVLTree | BinarySearchTree

trees.binary_trees.traversal.inorder_traverse(tree: AVLTree | BinarySearchTree, recursive: bool = True) → Iterator[Tuple[Any, Any]]

Perform In-Order traversal.

In-order traversal traverses a tree by the order: left subtree, current node, right subtree (LDR)

Parameters:

tree (SupportedTreeType) – A type of binary tree.
recursive (bool) – Perform traversal recursively or not.

Yields:

Pairs – The next (key, data) pair in the in-order traversal.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> from trees.binary_trees import traversal
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> [item for item in traversal.inorder_traverse(tree)]
[(1, '1'), (4, '4'), (7, '7'), (11, '11'), (15, '15'), (20, '20'),
 (22, '22'), (23, '23'), (24, '24'), (30, '30'), (34, '34')]

trees.binary_trees.traversal.levelorder_traverse(tree: AVLTree | BinarySearchTree) → Iterator[Tuple[Any, Any]]

Perform Level-Order traversal.

Level-order traversal traverses a tree: level by level, from left to right, starting from the root node.

Parameters:: tree (SupportedTreeType) – A type of binary tree.
Yields:: Pairs – The next (key, data) pair in the level-order traversal.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> from trees.binary_trees import traversal
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> [item for item in traversal.levelorder_traverse(tree)]
[(23, '23'), (4, '4'), (30, '30'), (1, '1'), (11, '11'), (24, '24'),
 (34, '34'), (7, '7'), (20, '20'), (15, '15'), (22, '22')]

trees.binary_trees.traversal.postorder_traverse(tree: AVLTree | BinarySearchTree, recursive: bool = True) → Iterator[Tuple[Any, Any]]

Perform Post-Order traversal.

Post-order traversal traverses a tree by the order: left subtree, right subtree, current node (LRD)

Parameters:

tree (SupportedTreeType) – A type of binary tree.
recursive (bool) – Perform traversal recursively or not.

Yields:

Pairs – The next (key, data) pair in the post-order traversal.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> from trees.binary_trees import traversal
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> [item for item in traversal.postorder_traverse(tree)]
[(1, '1'), (7, '7'), (15, '15'), (22, '22'), (20, '20'), (11, '11'),
 (4, '4'), (24, '24'), (34, '34'), (30, '30'), (23, '23')]

trees.binary_trees.traversal.preorder_traverse(tree: AVLTree | BinarySearchTree, recursive: bool = True) → Iterator[Tuple[Any, Any]]

Perform Pre-Order traversal.

Pre-order traversal traverses a tree by the order: current node, left subtree, right subtree (DLR)

Parameters:

tree (SupportedTreeType) – A type of binary tree.
recursive (bool) – Perform traversal recursively or not.

Yields:

Pairs – The next (key, data) pair in the pre-order traversal.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> from trees.binary_trees import traversal
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> [item for item in traversal.preorder_traverse(tree)]
[(23, '23'), (4, '4'), (1, '1'), (11, '11'), (7, '7'), (20, '20'),
 (15, '15'), (22, '22'), (30, '30'), (24, '24'), (34, '34')]

trees.binary_trees.traversal.reverse_inorder_traverse(tree: AVLTree | BinarySearchTree, recursive: bool = True) → Iterator[Tuple[Any, Any]]

Perform reversed In-Order traversal.

Reversed in-order traversal traverses a tree by the order: right subtree, current node, left subtree (RNL)

Parameters:

tree (SupportedTreeType) – A type of binary tree.
recursive (bool) – Perform traversal recursively or not.

Yields:

Pairs – The next (key, data) pair in the reversed in-order traversal.

Examples

>>> from trees.binary_trees import binary_search_tree
>>> from trees.binary_trees import traversal
>>> tree = binary_search_tree.BinarySearchTree()
>>> tree.insert(key=23, data="23")
>>> tree.insert(key=4, data="4")
>>> tree.insert(key=30, data="30")
>>> tree.insert(key=11, data="11")
>>> tree.insert(key=7, data="7")
>>> tree.insert(key=34, data="34")
>>> tree.insert(key=20, data="20")
>>> tree.insert(key=24, data="24")
>>> tree.insert(key=22, data="22")
>>> tree.insert(key=15, data="15")
>>> tree.insert(key=1, data="1")
>>> [item for item in traversal.reverse_inorder_traverse(tree)]
[(34, '34'), (30, '30'), (24, '24'), (23, '23'), (22, '22'), (20, '20'),
 (15, '15'), (11, '11'), (7, '7'), (4, '4'), (1, '1')]