➰ 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	ZigZag Traversal	Breadth-First Search
Tree	ZigZag Group Traversal	Breadth-First Search
DAG	General	Depth-First Search

bigtree.utils.iterators

inorder_iter

inorder_iter(tree, filter_condition=None, max_depth=0)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BinaryNode`	input tree	required
`filter_condition`	`Optional[Callable[[BinaryNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, optional	`0`

Returns:

Type	Description
`Iterable[BinaryNodeT]`	(Iterable[BinaryNode])

preorder_iter

preorder_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`Union[BaseNode, DAGNode]`	input tree	required
`filter_condition`	`Optional[Callable[[T], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[T], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, optional	`0`

Returns:

Type	Description
`Iterable[T]`	(Union[Iterable[BaseNode], Iterable[DAGNode]])

postorder_iter

postorder_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BaseNode`	input tree	required
`filter_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, optional	`0`

Returns:

Type	Description
`Iterable[BaseNodeT]`	(Iterable[BaseNode])

levelorder_iter

levelorder_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

Iterate through all children of a tree.

Level-Order Iteration Algorithm 1. Recursively traverse the nodes on same level.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BaseNode`	input tree	required
`filter_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, defaults to None	`0`

Returns:

Type	Description
`Iterable[BaseNodeT]`	(Iterable[BaseNode])

levelordergroup_iter

levelordergroup_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BaseNode`	input tree	required
`filter_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, defaults to None	`0`

Returns:

Type	Description
`Iterable[Iterable[BaseNodeT]]`	(Iterable[Iterable[BaseNode]])

zigzag_iter

zigzag_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BaseNode`	input tree	required
`filter_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, defaults to None	`0`

Returns:

Type	Description
`Iterable[BaseNodeT]`	(Iterable[BaseNode])

zigzaggroup_iter

zigzaggroup_iter(
    tree,
    filter_condition=None,
    stop_condition=None,
    max_depth=0,
)

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.

Examples:

>>> 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:

Name	Type	Description	Default
`tree`	`BaseNode`	input tree	required
`filter_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Return node if condition evaluates to `True`	`None`
`stop_condition`	`Optional[Callable[[BaseNode], bool]]`	function that takes in node as argument, optional Stops iteration if condition evaluates to `True`	`None`
`max_depth`	`int`	maximum depth of iteration, based on `depth` attribute, defaults to None	`0`

Returns:

Type	Description
`Iterable[Iterable[BaseNodeT]]`	(Iterable[Iterable[BaseNode]])

dag_iterator

dag_iterator(dag)

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.

Visit the current node.
Recursively traverse the current node's parents.
Recursively traverse the current node's children.

Examples:

>>> 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:

Name	Type	Description	Default
`dag`	`DAGNode`	input dag	required

Returns:

Type	Description
`Iterable[Tuple[DAGNodeT, DAGNodeT]]`	(Iterable[Tuple[DAGNode, DAGNode]])