Traversing a Tree (Data Structures)

Short stop on memory lane:

Data Types:

There are many types of data structures in programming, some of the most common include:

1. Arrays: a collection of elements of the same data type, stored in a contiguous memory location.
2. Linked Lists: a collection of elements, each containing a reference to the next element in the list.
3. Stacks: a last-in, first-out (LIFO) data structure.
4. Queues: a first-in, first-out (FIFO) data structure.
5. Trees: a hierarchical data structure that can be used to represent hierarchical relationships.
6. Graphs: a non-linear data structure that can be used to represent relationships between entities.
7. Hash tables: a data structure that stores elements in an associative array, using a hash function to map keys to indices in an array.
8. Heaps: a specialized tree-based data structure that satisfies the heap property: either the parent is greater than or equal to its children (max-heap) or the parent is less than or equal to its children (min-heap)
9. Trie: a tree-based data structure, which is used for efficient retrieval of a key in a large data set of strings
10. Bloom Filter: a probabilistic data structure that is used to test whether an element is a member of a set.

Trees are a hierarchical data structure, and there are several ways to traverse the nodes of a tree.

Two common types of traversals are:

Depth-first traversal: This involves traversing the tree by going as deep as possible along each branch before backtracking. There are three ways of doing a depth-first traversal:

• In-order traversal: visits the left subtree, then the root, and then the right subtree.

def inOrder(root):
    if root:
        inOrder(root.left)
        print(root.data, end=' ')
        inOrder(root.right)

• Pre-order traversal: visits the root, then the left subtree, and then the right subtree.

def preOrder(root):
    if root:
        print(root.data, end=' ')
        preOrder(root.left)
        preOrder(root.right)

• Post-order traversal: visits the left subtree, then the right subtree, and then the root.

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print(root.data, end=' ')

The previous solutions I provided use recursion which are a simpler and more elegant way of traversing the tree.

Breadth-first traversal: This involves traversing the tree level by level, visiting all the nodes at a given level before moving on to the next level. Breadth-first traversal is also known as level order traversal.

from collections import deque

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

def breadth_first_traversal(root):
    if root is None:
        return
    queue = deque()
    queue.append(root)
    while queue:
        node = queue.popleft()
        print(node.value, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
breadth_first_traversal(root) 
# Output: 1 2 3 4 5

In the above example, breadth_first_traversal function takes a root node of a tree, and using a queue, it visits all the nodes at a given level before moving on to the next level. The function uses a deque from the collections module, it appends the root to the queue and while the queue is not empty, it pops the leftmost element, prints it and appends its children to the queue. The example tree is a simple binary tree where each node has at most two children. It's worth noting that if the tree was a graph with unordered edges, you would have to keep track of the visited nodes to avoid infinite loop.

Both of the above traversals can be used depending on the specific task and the requirement of the application.

It’s worth noting that Depth-first traversal can be implemented using recursion, while Breadth-first traversal can be implemented using a queue.

Bogdan Tudorache | Founder @ berrynews.org

If you like the article and would like to support me, make sure to:

👏 Clap for the story (50 Claps) to help this article be featured

🔔 Follow me Bogdan Tudorache

📰 Read more coding content on Coding Challenge

🔔 Connect w/ me: LinkedIn | Reddit

Photo credits.