➰ Iterators

Iterator methods for Trees and DAGs.

Iterator Methods

Data Structure	Algorithm	Description
Binary Tree	In-order Traversal	Depth-First Search, LNR
Tree	Pre-order Traversal	Depth-First Search, NLR
Tree	Post-Order Traversal	Depth-First Search, LRN
Tree	Level-Order Traversal	Breadth-First Search
Tree	Level-Order Group Traversal	Breadth-First Search
Tree	ZigZag Traversal	Breadth-First Search
Tree	ZigZag Group Traversal	Breadth-First Search
DAG	General	Depth-First Search

Functions:

dag_iterator(dag)	Iterate through all nodes of a Directed Acyclic Graph (DAG).
inorder_iter(tree[, filter_condition, max_depth])	Iterate through all children of a tree.
levelorder_iter(tree[, filter_condition, ...])	Iterate through all children of a tree.
levelordergroup_iter(tree[, ...])	Iterate through all children of a tree.
postorder_iter(tree[, filter_condition, ...])	Iterate through all children of a tree.
preorder_iter(tree[, filter_condition, ...])	Iterate through all children of a tree.
zigzag_iter(tree[, filter_condition, ...])	Iterate through all children of a tree.
zigzaggroup_iter(tree[, filter_condition, ...])	Iterate through all children of a tree.

bigtree.utils.iterators.dag_iterator(dag: DAGNodeT) → Iterable[Tuple[DAGNodeT, DAGNodeT]]

Iterate through all nodes of a Directed Acyclic Graph (DAG). Note that node names must be unique. Note that DAG must at least have two nodes to be shown on graph.

1. Visit the current node.

2. Recursively traverse the current node’s parents.

3. Recursively traverse the current node’s children.

>>> from bigtree import DAGNode, dag_iterator
>>> a = DAGNode("a", step=1)
>>> b = DAGNode("b", step=1)
>>> c = DAGNode("c", step=2, parents=[a, b])
>>> d = DAGNode("d", step=2, parents=[a, c])
>>> e = DAGNode("e", step=3, parents=[d])
>>> [(parent.node_name, child.node_name) for parent, child in dag_iterator(a)]
[('a', 'c'), ('a', 'd'), ('b', 'c'), ('c', 'd'), ('d', 'e')]

Parameters:

dag (DAGNode) – input dag

Returns:

(Iterable[Tuple[DAGNode, DAGNode]])

bigtree.utils.iterators.inorder_iter(tree: BinaryNodeT, filter_condition: Callable[[BinaryNodeT], bool] | None = None, max_depth: int = 0) → Iterable[BinaryNodeT]

Iterate through all children of a tree.

In-Order Iteration Algorithm, LNR

1. Recursively traverse the current node’s left subtree.

2. Visit the current node.

3. Recursively traverse the current node’s right subtree.

>>> from bigtree import BinaryNode, list_to_binarytree, inorder_iter
>>> num_list = [1, 2, 3, 4, 5, 6, 7, 8]
>>> root = list_to_binarytree(num_list)
>>> root.show()
1
├── 2
│   ├── 4
│   │   └── 8
│   └── 5
└── 3
    ├── 6
    └── 7

>>> [node.node_name for node in inorder_iter(root)]
['8', '4', '2', '5', '1', '6', '3', '7']

>>> [node.node_name for node in inorder_iter(root, filter_condition=lambda x: x.node_name in ["1", "4", "3", "6", "7"])]
['4', '1', '6', '3', '7']

>>> [node.node_name for node in inorder_iter(root, max_depth=3)]
['4', '2', '5', '1', '6', '3', '7']

Parameters:

• tree (BinaryNode) – input tree

• filter_condition (Optional[Callable[[BinaryNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, optional

Returns:

(Iterable[BinaryNode])

bigtree.utils.iterators.levelorder_iter(tree: BaseNodeT, filter_condition: Callable[[BaseNodeT], bool] | None = None, stop_condition: Callable[[BaseNodeT], bool] | None = None, max_depth: int = 0) → Iterable[BaseNodeT]

Iterate through all children of a tree.

Level-Order Iteration Algorithm

1. Recursively traverse the nodes on same level.

>>> from bigtree import Node, list_to_tree, levelorder_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [node.node_name for node in levelorder_iter(root)]
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

>>> [node.node_name for node in levelorder_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
['a', 'd', 'e', 'f', 'g']

>>> [node.node_name for node in levelorder_iter(root, stop_condition=lambda x: x.node_name == "e")]
['a', 'b', 'c', 'd', 'f']

>>> [node.node_name for node in levelorder_iter(root, max_depth=3)]
['a', 'b', 'c', 'd', 'e', 'f']

Parameters:

• tree (BaseNode) – input tree

• filter_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, defaults to None

Returns:

(Iterable[BaseNode])

bigtree.utils.iterators.levelordergroup_iter(tree: BaseNodeT, filter_condition: Callable[[BaseNodeT], bool] | None = None, stop_condition: Callable[[BaseNodeT], bool] | None = None, max_depth: int = 0) → Iterable[Iterable[BaseNodeT]]

Iterate through all children of a tree.

Level-Order Group Iteration Algorithm

1. Recursively traverse the nodes on same level, returns nodes level by level in a nested list.

>>> from bigtree import Node, list_to_tree, levelordergroup_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [[node.node_name for node in group] for group in levelordergroup_iter(root)]
[['a'], ['b', 'c'], ['d', 'e', 'f'], ['g', 'h']]

>>> [[node.node_name for node in group] for group in levelordergroup_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
[['a'], [], ['d', 'e', 'f'], ['g']]

>>> [[node.node_name for node in group] for group in levelordergroup_iter(root, stop_condition=lambda x: x.node_name == "e")]
[['a'], ['b', 'c'], ['d', 'f']]

>>> [[node.node_name for node in group] for group in levelordergroup_iter(root, max_depth=3)]
[['a'], ['b', 'c'], ['d', 'e', 'f']]

Parameters:

• tree (BaseNode) – input tree

• filter_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, defaults to None

Returns:

(Iterable[Iterable[BaseNode]])

bigtree.utils.iterators.postorder_iter(tree: BaseNodeT, filter_condition: Callable[[BaseNodeT], bool] | None = None, stop_condition: Callable[[BaseNodeT], bool] | None = None, max_depth: int = 0) → Iterable[BaseNodeT]

Iterate through all children of a tree.

Post-Order Iteration Algorithm, LRN

1. Recursively traverse the current node’s left subtree.

2. Recursively traverse the current node’s right subtree.

3. Visit the current node.

>>> from bigtree import Node, list_to_tree, postorder_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [node.node_name for node in postorder_iter(root)]
['d', 'g', 'h', 'e', 'b', 'f', 'c', 'a']

>>> [node.node_name for node in postorder_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
['d', 'g', 'e', 'f', 'a']

>>> [node.node_name for node in postorder_iter(root, stop_condition=lambda x: x.node_name == "e")]
['d', 'b', 'f', 'c', 'a']

>>> [node.node_name for node in postorder_iter(root, max_depth=3)]
['d', 'e', 'b', 'f', 'c', 'a']

Parameters:

• tree (BaseNode) – input tree

• filter_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, optional

Returns:

(Iterable[BaseNode])

bigtree.utils.iterators.preorder_iter(tree: T, filter_condition: Callable[[T], bool] | None = None, stop_condition: Callable[[T], bool] | None = None, max_depth: int = 0) → Iterable[T]

Iterate through all children of a tree.

Pre-Order Iteration Algorithm, NLR

1. Visit the current node.

2. Recursively traverse the current node’s left subtree.

3. Recursively traverse the current node’s right subtree.

It is topologically sorted because a parent node is processed before its child nodes.

>>> from bigtree import Node, list_to_tree, preorder_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [node.node_name for node in preorder_iter(root)]
['a', 'b', 'd', 'e', 'g', 'h', 'c', 'f']

>>> [node.node_name for node in preorder_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
['a', 'd', 'e', 'g', 'f']

>>> [node.node_name for node in preorder_iter(root, stop_condition=lambda x: x.node_name == "e")]
['a', 'b', 'd', 'c', 'f']

>>> [node.node_name for node in preorder_iter(root, max_depth=3)]
['a', 'b', 'd', 'e', 'c', 'f']

Parameters:

• tree (Union[BaseNode, DAGNode]) – input tree

• filter_condition (Optional[Callable[[T], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[T], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, optional

Returns:

(Union[Iterable[BaseNode], Iterable[DAGNode]])

bigtree.utils.iterators.zigzag_iter(tree: BaseNodeT, filter_condition: Callable[[BaseNodeT], bool] | None = None, stop_condition: Callable[[BaseNodeT], bool] | None = None, max_depth: int = 0) → Iterable[BaseNodeT]

Iterate through all children of a tree.

ZigZag Iteration Algorithm

1. Recursively traverse the nodes on same level, in a zigzag manner across different levels.

>>> from bigtree import Node, list_to_tree, zigzag_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [node.node_name for node in zigzag_iter(root)]
['a', 'c', 'b', 'd', 'e', 'f', 'h', 'g']

>>> [node.node_name for node in zigzag_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
['a', 'd', 'e', 'f', 'g']

>>> [node.node_name for node in zigzag_iter(root, stop_condition=lambda x: x.node_name == "e")]
['a', 'c', 'b', 'd', 'f']

>>> [node.node_name for node in zigzag_iter(root, max_depth=3)]
['a', 'c', 'b', 'd', 'e', 'f']

Parameters:

• tree (BaseNode) – input tree

• filter_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, defaults to None

Returns:

(Iterable[BaseNode])

bigtree.utils.iterators.zigzaggroup_iter(tree: BaseNodeT, filter_condition: Callable[[BaseNodeT], bool] | None = None, stop_condition: Callable[[BaseNodeT], bool] | None = None, max_depth: int = 0) → Iterable[Iterable[BaseNodeT]]

Iterate through all children of a tree.

ZigZag Group Iteration Algorithm

1. Recursively traverse the nodes on same level, in a zigzag manner across different levels,

   returns nodes level by level in a nested list.

>>> from bigtree import Node, list_to_tree, zigzaggroup_iter
>>> path_list = ["a/b/d", "a/b/e/g", "a/b/e/h", "a/c/f"]
>>> root = list_to_tree(path_list)
>>> root.show()
a
├── b
│   ├── d
│   └── e
│       ├── g
│       └── h
└── c
    └── f

>>> [[node.node_name for node in group] for group in zigzaggroup_iter(root)]
[['a'], ['c', 'b'], ['d', 'e', 'f'], ['h', 'g']]

>>> [[node.node_name for node in group] for group in zigzaggroup_iter(root, filter_condition=lambda x: x.node_name in ["a", "d", "e", "f", "g"])]
[['a'], [], ['d', 'e', 'f'], ['g']]

>>> [[node.node_name for node in group] for group in zigzaggroup_iter(root, stop_condition=lambda x: x.node_name == "e")]
[['a'], ['c', 'b'], ['d', 'f']]

>>> [[node.node_name for node in group] for group in zigzaggroup_iter(root, max_depth=3)]
[['a'], ['c', 'b'], ['d', 'e', 'f']]

Parameters:

• tree (BaseNode) – input tree

• filter_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Return node if condition evaluates to True

• stop_condition (Optional[Callable[[BaseNode], bool]]) – function that takes in node as argument, optional Stops iteration if condition evaluates to True

• max_depth (int) – maximum depth of iteration, based on depth attribute, defaults to None

Returns:

(Iterable[Iterable[BaseNode]])