Binary Tree Traversals


Binary Tree Traversals refer to the methods of visiting and processing the nodes of a binary tree in a specific order. There are three common types of binary tree traversals: pre-order, in-order, and post-order. Each traversal follows a specific order of visiting the nodes.

Example: Let's create a binary tree and perform the three types of traversals.

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

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Pre-order traversal
def pre_order(node):
    if node is None:
        return
    print(node.value)  # Process the current node
    pre_order(node.left)  # Traverse left subtree
    pre_order(node.right)  # Traverse right subtree

print("Pre-order traversal:")
pre_order(root)
# Output: 1 2 4 5 3

# In-order traversal
def in_order(node):
    if node is None:
        return
    in_order(node.left)  # Traverse left subtree
    print(node.value)  # Process the current node
    in_order(node.right)  # Traverse right subtree

print("In-order traversal:")
in_order(root)
# Output: 4 2 5 1 3

# Post-order traversal
def post_order(node):
    if node is None:
        return
    post_order(node.left)  # Traverse left subtree
    post_order(node.right)  # Traverse right subtree
    print(node.value)  # Process the current node

print("Post-order traversal:")
post_order(root)
# Output: 4 5 2 3 1

In this example, we define a Node class that represents a node in the binary tree. Each node has a value, left child, and right child.

We create a binary tree with the given values.

Pre-order Traversal: The pre-order traversal visits the nodes in the following order: root, left subtree, right subtree. In the pre_order function, we perform the following steps:

  • If the current node is None, it means we have reached a null node, so we return.
  • We process the value of the current node (print or perform any desired operation).
  • We recursively call pre_order on the left child to traverse the left subtree.
  • We recursively call pre_order on the right child to traverse the right subtree.

In-order Traversal: The in-order traversal visits the nodes in the following order: left subtree, root, right subtree. In the in_order function, we perform the following steps:

  • If the current node is None, it means we have reached a null node, so we return.
  • We recursively call in_order on the left child to traverse the left subtree.
  • We process the value of the current node (print or perform any desired operation).
  • We recursively call in_order on the right child to traverse the right subtree.

Post-order Traversal: The post-order traversal visits the nodes in the following order: left subtree, right subtree, root. In the post_order function, we perform the following steps:

  • If the current node is None, it means we have reached a null node, so we return.
  • We recursively call post_order on the left child to traverse the left subtree.
  • We recursively call post_order on the right child to traverse the right subtree.
  • We process the value of the current node (print or perform any desired operation).

Let's solve a question using the concept of binary tree traversals. The question is "Binary Tree Zigzag Level Order Traversal," which requires traversing a binary tree in a zigzag pattern and returning the values at each level.

from collections import deque

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

class Solution:
    def zigzag_level_order(self, root):
        if root is None:
            return []
        
        result = []
        queue = deque([root])
        level = 0
        
        while queue:
            level_values = deque()
            level_length = len(queue)
            
            for _ in range(level_length):
                node = queue.popleft()
                
                if level % 2 == 0:
                    level_values.append(node.value)
                else:
                    level_values.appendleft(node.value)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(list(level_values))
            level += 1
        
        return result

# Create an instance of Solution
solution = Solution()

# Create a binary tree
root = Node(3)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.right = Node(7)

# Perform zigzag level order traversal
zigzag_order = solution.zigzag_level_order(root)
print(zigzag_order)
# Output: [[3], [20, 9], [15, 7]]

In this solution, we define a Node class to represent a node in the binary tree. We also define a Solution class that contains the zigzag_level_order method to perform the zigzag level order traversal of the binary tree.

The zigzag_level_order method is implemented using a queue to perform level order traversal. We start by checking if the root is None and returning an empty list in that case. We initialize an empty result list to store the level order traversal results.

We use a deque, queue, to store the nodes to be processed. We start with the root node and set the initial level to 0.

While there are nodes in the queue, we perform the following steps:

  • Initialize an empty deque, level_values, to store the values of the nodes at the current level.
  • Get the number of nodes in the current level, level_length, using the length of the queue.
  • Iterate level_length times to process each node in the current level:
    • Remove the node from the left end of the queue.
    • If the current level is even, append the value of the node to level_values from the right end.
    • If the current level is odd, append the value of the node to level_values from the left end.
    • If the node has a left child, append it to the right end of the queue.
    • If the node has a right child, append it to the right end of the queue.
  • Convert level_values to a list and append it to the result list.
  • Increment the level by 1.

Finally, we return the result list, which contains the zigzag level order traversal of the binary tree.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree. This is because we store the nodes at each level in the queue, and in the worst case, the maximum number of nodes in a level would be m.

 

Next Post Previous Post