gopythonrust

If you partook in the beginner lessons in software development, we will be familiar with binary trees. We will explore this topic more in depth in this section. To begin, why don't we review what a tree looks like.

A binary tree consists of nodes where each node at a minimum contains some data as well as a pointer for a left and right child. Given a root node, we may traverse the tree in various ways to extract information.

We also define a node and a way to construct a tree from a list of nodes as following.

class Node: def __init__(self, value, left=None, right=None, target=False): self.value = value self.left = left self.right = right def __str__(self): left_val = self.left.value if self.left else self.left right_val = self.right.value if self.right else self.right return f"Node({self.value}, left={left_val}, right={right_val})" def to_binary_tree(items: list[int]) -> Node: # create binary tree from list of values n = len(items) if n == 0: return None def inner(index: int = 0) -> Node: # closure function using recursion to build tree if n <= index or items[index] is None: return None node = Node(items[index]) node.left = inner(2 * index + 1) node.right = inner(2 * index + 2) return node return inner()

Using recursion, there are three methods for traversal, where the primary distinction is the order in which nodes are visited:

• pre-order: A current node is visited first, followed by a left subtree and then a right subtree.
• in-order: A left subtree is visited first, followed by a current node, and then a right subtree.
• post-order: A left subtree is visited first, followed by a right subtree, and then a current node.

We will look at an example along with a relative strength for each.