BST Traversal

Basically, there are three methods of tree traversal: pre-order, in-order, and post-order traversal. The difference between the three methods is in the order of elements. Let's see how we achieve this in code.
In this chapter we will work with the following tree:

The pre-order traversal

The pre-order traversal yields the natural ordering. First, we visit the root node and then recursively each subtree's left and right subtrees.


              12345678910111213141516171819202122232425262728293031323334353637
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85)))

# The pre-order traversal yields the natural ordering of the elements in the tree
def pre_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, append its value to the list
        if node is not None:
            nodes.append(str(node.value))
            # Recursively traverse the left and right subtrees
            traverse(node.left)
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform pre-order traversal and print the result
print(pre_order_traversal(root))

We put the append statement before the recursive calls to achieve this.

The in-order traversal

The in-order traversal is probably the most common, as it yields the sorted order of the elements in the tree.


              12345678910111213141516171819202122232425262728293031323334353637383940
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The in-order traversal yields the sorted order of the elements in the tree
def in_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # Append the node value to the list
        nodes.append(str(node.value))
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform in-order traversal and print the result
print(in_order_traversal(root))

When implementing an in-order traversal, we put the append statement in the middle between two recursive calls on the left and the right subtrees.

The post-order traversal

The third way to traverse a Binary Search Tree is to use the post-order traversal. The post-order traversal algorithm first visits the left and the right subtree and then visits the root node for each subtree in the initial tree.


              1234567891011121314151617181920212223242526272829303132333435363738394041
            
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Tree(26, 
            left=Tree(12, 
                      left=Tree(7), 
                      right=Tree(24)), 
            right=Tree(52, 
                       left=Tree(39), 
                       right=Tree(85
                       )))

# The post-order traversal prints the elements in order from bottom to the top
# from left to the right
def post_order_traversal(subtree_root):
    # Initialize an empty string to store the node values
    nodes = []

    # Define the recursive function to traverse the tree
    def traverse(node):
        # If the node is not None, recursively traverse the left subtree
        if node.left:
            traverse(node.left)
        # If the node is not None, recursively traverse the right subtree
        if node.right:
            traverse(node.right)
        # Append the node value to the list
        nodes.append(str(node.value))

    # Start the traversal from the root
    traverse(subtree_root)

    # Join the node values with the arrow separator
    result = ' -> '.join(nodes)
    return result

# Perform post-order traversal and print the result
print(post_order_traversal(root))

We append the nodes after the recursive calls to implement the post-order traversal.

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 4. Розділ 5