Binary-tree traversal · HL application

An in-order traversal visits the left subtree, the node, then the right subtree.

1visits = []23def tree_traversal(node):4    if node is None:5        return6    tree_traversal(node["left"])7    visits.append(node["value"])8    tree_traversal(node["right"])

B2.4.4 application, not a B2.4.5 branching-code requirement. Each dictionary represents a node; None means no child. This particular tree is a binary search tree, so in-order traversal produces sorted output. Each node is visited once: O(n) time, O(h) auxiliary stack space for tree height h, excluding the output log.