Tree Traversal - Naukri Code 360

Introduction

Trees are an important data structure in computer science & programming. They allow us to organize data in a hierarchical way, with nodes connected by edges. To access & process the data stored in a tree, we need ways to systematically visit each node. This is where tree traversal comes in. Tree traversal refers to the process of visiting each node in a tree data structure in a specific order. There are different techniques for traversing a tree, each with its own characteristics & use cases.

In this article, we will discuss the main types of tree traversal: inorder, preorder, postorder, & level order traversal. We'll look at how they work, their implementations in code, & examples of when to use each one.

What is Tree Traversal?

Tree traversal refers to the process of visiting each node in a tree structure, exactly once, in a systematic way. This process is essential because it allows us to access, inspect, and modify the data each node contains. Understanding tree traversal is critical for applications like parsing expressions in a compiler, organizing data in databases, and navigating hierarchies in file systems.

Trees consist of nodes connected by edges, with one node designated as the root, where the traversal begins. Each node can have zero or more child nodes, which can further branch into more nodes. The goal of traversal is to reach every node without repetition. The method of traversal depends on the specific needs of the application, such as whether to visit parent nodes before their children or vice versa.

The traversal techniques mainly differ in the order they visit the nodes: from left to right, depth-first, or breadth-first.

Tree Traversal Techniques

When traversing a tree, the pattern in which nodes are accessed can significantly impact the performance & outcomes of the traversal. Let's explore the main techniques used for tree traversal, each with its own set of rules & purposes:

Depth-First Search (DFS): This method explores as far as possible along each branch before backing up. It’s particularly useful for tasks that need to visit children before their respective parents are revisited.
Breadth-First Search (BFS): Unlike DFS, BFS explores all the neighbors at the present depth prior to moving on to nodes at the next depth level. This approach is excellent for finding the shortest path on unweighted graphs.

These two primary methods can be implemented in several specific ways depending on the requirement, such as Inorder, Preorder, Postorder, & Level Order traversal, which are particularly common in binary trees.

Inorder Traversal: Visits the left subtree, the root node, & then the right subtree. This is often used in binary search trees where such a traversal returns values in non-decreasing order.
Preorder Traversal: Visits the root node first, then the left subtree, & finally the right subtree. It’s useful for creating a copy of the tree.
Postorder Traversal: Visits the children nodes before the parent node. This method is useful for deleting or freeing the space of the tree starting from the leaves up to the root.
Level Order Traversal: Visits every node on the same level from left to right, which is useful for scenarios like printing nodes in the view from top to bottom.

Inorder Traversal

Inorder traversal is a specific technique used primarily in binary trees. This method involves visiting the left subtree first, then the node itself, and finally the right subtree. It is particularly valued in binary search trees (BSTs), where it guarantees that nodes are visited in ascending order, which is crucial for operations like displaying sorted data directly from the tree structure.

How Inorder Traversal Works

Start at the Root: Begin at the root node, but instead of processing it first, move to the left child.
Visit Left Subtree: Continue moving left recursively until you reach a node with no left child.
Visit Node: Process the current node's value. This typically means printing the value or storing it.
Visit Right Subtree: Move to the right child of the node and repeat the process for the subtree rooted at this child.

Code Example in Python

Python

Python


def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)  # Recursively visit left subtree
        print(node.value)             # Process the current node
        inorder_traversal(node.right) # Recursively visit right subtree

# Assuming a simple Binary Tree Node class
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# Constructing a simple tree: 
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
# Output will be: 2, 1, 3
inorder_traversal(root)

You can also try this code with Online Python Compiler

Run Code

Output

2
1
3

This code snippet demonstrates the process of Inorder traversal on a basic binary tree, resulting in the values being printed in the order they are visited.

Inorder traversal is helpful not just for binary search trees but also in applications where an ordered output is necessary, making it a versatile tool in tree-related operations.

Preorder Traversal

Preorder traversal is another method used to visit all the nodes in a tree, specifically useful when you need to explore roots before inspecting leaves. It’s particularly effective for scenarios where you want to replicate or print the structure of a tree, as it records nodes in the exact order that allows you to recreate the tree later.

How Preorder Traversal Works

Visit Node: Start at the root and process the node (usually by printing or saving its value).
Visit Left Subtree: Move to the left child of the current node and perform Preorder traversal recursively.
Visit Right Subtree: After completing the left subtree, proceed to the right child and repeat the process.

Code Example in Python

Python

Python

def preorder_traversal(node):
    if node:
        print(node.value)             # Process the current node first
        preorder_traversal(node.left)  # Recursively visit left subtree
        preorder_traversal(node.right) # Recursively visit right subtree

# Assuming a simple Binary Tree Node class
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# Constructing a simple tree: 
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

# Output will be: 1, 2, 3
preorder_traversal(root)

You can also try this code with Online Python Compiler

Run Code

Output

1
2
3

This method is straightforward: by visiting the root first and then its children, it ensures that each subtree is completely processed before moving on to the next subtree. This approach is beneficial for operations like copying the tree where the tree’s exact structure needs to be preserved.

Preorder traversal is simple yet powerful, providing the means to handle many practical applications efficiently.

Postorder Traversal

Postorder traversal is a technique that ensures that a node is visited after its subtrees have been visited and processed. This method is particularly useful in scenarios where you need to perform operations that depend on the results from the subtrees, such as evaluating the expression trees or freeing up memory used by the tree starting from the leaves.

How Postorder Traversal Works:

Visit Left Subtree: Begin at the root, but rather than processing it, first move to and recursively traverse the left subtree.
Visit Right Subtree: After completing the left subtree, move to the right subtree and perform a similar traversal.
Visit Node: Once both subtrees have been visited, process the current node.
This order ensures that a node is only processed after all its children have been handled, which is crucial for operations like safely deleting nodes.

Code Example in Python

Python

Python

def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)  # Recursively visit left subtree
        postorder_traversal(node.right) # Recursively visit right subtree
        print(node.value)               # Process the current node last

# Assuming a simple Binary Tree Node class
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# Constructing a simple tree: 
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

# Output will be: 2, 3, 1
postorder_traversal(root)

You can also try this code with Online Python Compiler

Run Code

Output

2
3
1

This traversal pattern is optimal for tree deletion: by handling the children first, it ensures that no references are lost prematurely, allowing for safe and effective tree cleanup or result calculation.

Postorder traversal, with its methodical approach to handling subtrees first, is invaluable for many applications that require post-processing of data.

Level Order Traversal

Level order traversal, also known as breadth-first search (BFS) for trees, processes nodes level by level, starting from the root. This method is particularly useful when you need to process a tree layer by layer, as it can help in scenarios such as printing nodes in a way that mirrors the tree's layer structure, or in finding the shortest path in certain tree-based algorithms.

How Level Order Traversal Works:

Start at the Root: Begin with the root node.
Queue the Nodes: Utilize a queue to keep track of nodes. First, enqueue the root, and as you dequeue each node, also enqueue its children.
Process Sequentially: Process each node as it is dequeued, ensuring that nodes are handled in the order they appear in the tree from top to bottom and left to right.
This traversal ensures that all nodes at a particular depth are handled before any nodes at the next level are visited.

Code Example in Python:

Python

Python

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    queue = deque([root])  # Start with the root node in the queue
    while queue:
        node = queue.popleft()  # Remove from the front of the queue
        print(node.value)       # Process the current node
        if node.left:
            queue.append(node.left)  # Add left child to the queue
        if node.right:
            queue.append(node.right) # Add right child to the queue

# Assuming a simple Binary Tree Node class
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# Constructing a simple tree: 
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

# Output will be: 1, 2, 3
level_order_traversal(root)

You can also try this code with Online Python Compiler

Run Code

Output

1
2
3

This method is highly effective for certain types of problems, such as those that require a view of the tree one level at a time, ensuring a comprehensive and organized traversal.

Other Tree Traversals

Besides the main traversal methods discussed, there are additional specialized techniques used to meet specific needs. Understanding these can be particularly useful for complex tree structures where standard approaches may not suffice.

Spiral Order Traversal

Spiral order traversal visits nodes in a zigzag pattern, alternating between levels. This is useful when you need to differentiate between levels visually or logically.

Code Example in Python

Python

Python

from collections import deque

def spiral_order_traversal(root):
    if not root:
        return
    result = []
    nodes = deque([root])
    left_to_right = True

    while nodes:
        level_size = len(nodes)
        level = deque()

        for _ in range(level_size):
            node = nodes.popleft()
            if left_to_right:
                level.append(node.value)
            else:
                level.appendleft(node.value)

            if node.left:
                nodes.append(node.left)
            if node.right:
                nodes.append(node.right)

        result.extend(level)
        left_to_right = not left_to_right  # Switch the direction

    return result

# Assuming a simple Binary Tree Node class
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# Constructing a simple tree:
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

# Output will be: [1, 3, 2]
print(spiral_order_traversal(root))

You can also try this code with Online Python Compiler

Run Code

Output

1
3
2

Morris Traversal

Morris Traversal is a method that allows tree traversal without extra space and without modifying the tree structure. It’s especially valuable when space complexity is a constraint.

Code Example in Python

def morris_traversal(root):
    current = root
    while current:
        if not current.left:
            print(current.value)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = null
                print(current.value)
                current = current.right
# Assuming the same TreeNode class
# Example usage:
# The output depends on the structure of the tree and might vary
print(morris_traversal(root))

These methods showcase the versatility and adaptability of tree traversals, proving that with the right approach, trees can be navigated to fulfill a wide range of requirements, from space efficiency to order specificity.

Frequently Asked Questions

What is the fastest tree traversal method?

The speed of traversal depends on the specific needs of the application. For instance, Level Order Traversal is fastest for breadth-first searches, whereas Inorder might be preferable for sorted data retrieval.

Can tree traversal be done without recursion?

Yes, tree traversal can be implemented iteratively using stacks for Depth-First methods or queues for Breadth-First methods like Level Order Traversal.

Why is Postorder Traversal used in deleting a tree?

Postorder ensures that all child nodes are processed before the parent node, making it safe to delete or free nodes without losing access to parts of the tree.

What is tree traversal DFS vs BFS?

Tree traversal techniques include Depth-First Search (DFS) and Breadth-First Search (BFS). DFS explores as far along a branch as possible before backtracking, while BFS examines all nodes at one depth level before moving to the next. DFS is implemented using recursion or a stack, whereas BFS uses a queue.

Conclusion

In this article, we have learned various methods of tree traversal, each with its unique characteristics & applications. We started with the basics of Inorder, Preorder, and Postorder traversals, which are foundational for understanding tree operations, we discussed Level Order Traversal for its layer-by-layer approach. We also talked about the specialized techniques like Spiral and Morris Traversal, enhancing our options for dealing with complex tree-based problems.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.