Pre-order, In-order and Post-order Traversal of Binary Trees in Python

Intro

The Tree data structure is similar to linked lists in that each node contains data and can be linked to other nodes. In a Tree, a single element can have multiple ‘next’ elements, allowing the data structure to branch out in various directions. The data structure is called a “tree” because it looks like a tree, only upside down. The Tree data structure can be useful in many cases:

• Hierarchical Data: File systems, organizational models, etc.
• Databases: Used for quick data retrieval.
• Routing Tables: Used for routing data in network algorithms.
• Sorting/Searching: Used for sorting data and searching for data.
• Priority Queues: Priority queue data structures are commonly implemented using trees, such as binary heaps.

Types of Trees

Trees are a fundamental data structure in computer science, used to represent hierarchical relationships.

• Binary Trees: Each node has up to two children, the left child node and the right child node. This structure is the foundation for more complex tree types like Binay Search Trees and AVL Trees.

• Binary Search Trees (BSTs): A type of Binary Tree where for each node, the left child node has a lower value, and the right child node has a higher value.

• AVL Trees: A type of Binary Search Tree that self-balances so that for every node, the difference in height between the left and right subtrees is at most one. This balance is maintained through rotations when nodes are inserted or deleted.

Binary Trees

A Binary Tree is a type of tree data structure where each node can have a maximum of two child nodes, a left child node and a right child node. This restriction, that a node can have a maximum of two child nodes, gives us many benefits:

• Algorithms like traversing, searching, insertion and deletion become easier to understand, to implement, and run faster.
• Keeping data sorted in a Binary Search Tree (BST) makes searching very efficient.
• Balancing trees is easier to do with a limited number of child nodes, using an AVL Binary Tree for example.
• Binary Trees can be represented as arrays, making the tree more memory efficient.

Types of Binary Trees

There are different variants, or types, of Binary Trees worth discussing to get a better understanding of how Binary Trees can be structured. Below are short explanations of different types of Binary Tree structures.

1. A balanced Binary Tree has at most 1 in difference between its left and right subtree heights, for each node in the tree.
2. A complete Binary Tree has all levels full of nodes, except the last level, which is can also be full, or filled from left to right. The properties of a complete Binary Tree means it is also balanced.
3. A full Binary Tree is a kind of tree where each node has either 0 or 2 child nodes.
4. A perfect Binary Tree has all leaf nodes on the same level, which means that all levels are full of nodes, and all internal nodes have two child nodes.The properties of a perfect Binary Tree means it is also full, balanced, and complete.

Implementation of Binary Trees

To avoid the cost of all the shifts in memory that we get from using Arrays, it is useful to implement Binary Trees with pointers from one element to the next, just like Binary Trees are implemented before this point, especially when the Binary Tree is modified often. But in case we read from the Binary Tree a lot more than we modify it, an Array implementation of a Binary Tree can make sense as it needs less memory, it can be easier to implement, and it can be faster for certain operations due to cache locality.

Consider this Binary Tree:

This Binary Tree can be stored in an Array starting with the root node R on index 0. The rest of the tree can be built by taking a node stored on index i, and storing its left child node on index 2⋅i + 1, and its right child node on index 2⋅i + 2. Below is an Array implementation of the Binary Tree. By comparing how these traversals are done in an array implementation to how the pointer implementation was traversed, you can see that the pre-order, in-order, and post-order traversals works in the same recursive way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']

def left_child_index(index):
    return 2 * index + 1

def right_child_index(index):
    return 2 * index + 2

def pre_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return [binary_tree_array[index]] + pre_order(left_child_index(index)) + pre_order(right_child_index(index))

def in_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return in_order(left_child_index(index)) + [binary_tree_array[index]] + in_order(right_child_index(index))

def post_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return post_order(left_child_index(index)) + post_order(right_child_index(index)) + [binary_tree_array[index]]

print("Pre-order Traversal:", pre_order(0))
print("In-order Traversal:", in_order(0))
print("Post-order Traversal:", post_order(0))

Algorithm, Binary Trees, Python — Jan 8, 2023