Skip to content

➰ 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 BinaryNodeT

input tree

 required
filter_condition Optional[Callable[[BinaryNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[BinaryNodeT]

Iterable of nodes

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 T

input tree

 required
filter_condition Optional[Callable[[T], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[T], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[T]

Iterable of nodes

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 BaseNodeT

input tree

 required
filter_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[BaseNodeT]

Iterable of nodes

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 BaseNodeT

input tree

 required
filter_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[BaseNodeT]

Iterable of nodes

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 BaseNodeT

input tree

 required
filter_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[Iterable[BaseNodeT]]

List of iterable of nodes

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 BaseNodeT

input tree

 required
filter_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[BaseNodeT]

Iterable of nodes

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 BaseNodeT

input tree

 required
filter_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Return node if condition evaluates to True

 None
stop_condition Optional[Callable[[BaseNodeT], bool]]

function that takes in node as argument. Stops iteration if condition evaluates to True

 None
max_depth int

maximum depth of iteration, based on depth attribute

 0

Returns:

Type Description
Iterable[Iterable[BaseNodeT]]

List of iterable of nodes

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.

DAG Iteration
  1. Visit the current node
  2. Recursively traverse the current node's parents
  3. 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 DAGNodeT

input dag

 required

Returns:

Type Description
Iterable[Tuple[DAGNodeT, DAGNodeT]]

Iterable of parent-child pair