# Preorder Traversal of Binary Tree ## Introduction to Preorder Traversal of Binary Traversal

Preorder traversal of Binary Tree is one of the fundamental techniques used to explore and manipulate binary trees, a data structure widely used in computer science and programming. This technique allows you to visit each node in a binary tree systematically, making it an essential tool for a variety of tasks like searching, insertion, and deletion.

## Methods of Tree Traversal

### There are three primary methods of tree traversal:

• Preorder Traversal
• Postorder Traversal
• Inorder Traversal

## Tree Traversal in Data Structure Examples ## Preorder Traversal of Binary Tree

Preorder traversal, also known as DLR (Data-Left-Right) traversal, is a depth-first traversal technique for binary trees. The name “preorder” signifies the order in which you visit the nodes of the tree. In preorder traversal, you start at the root node, then traverse the left subtree, and finally explore the right subtree.

## Visualization of Preorder Traversal ### Consider a binary tree : When conducting a preorder traversal within this binary tree, the sequence of steps unfolds as follows:

### Step 1 : The initial visitation targets the root, denoted as node 13. ### Step 2 : Subsequently, we proceed to explore the left subtree, leading to the visitation of the left subtree’s root, namely node 11. ### Step 3 : Again we have to traverse through the left sub-tree of node 11 i.e. node 9. ### Step 4 : Now we have to move to the right sub-tree of the node 11 i.e. node 12. ### Step 5 : The left sub-tree of node 13 is traversed. Now we have to visit the right sub-tree of the node 13 i.e. node 15. ### Step 6 : Now we have to traverse the left sub-tree of node 15 i.e. node 14. ### Step 7 : Traverse the right sub-tree of node 15 i.e. node 17. ### Code :

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

def recursive_preorder_traversal(node):
if node is not None:
# 1. Visit the current node
print(node.value)

# 2. Recursively traverse the left subtree
recursive_preorder_traversal(node.left)

# 3. Recursively traverse the right subtree
recursive_preorder_traversal(node.right)
```

### Preorder Traversal using Iterative Method(Using Stack)

```def iterative_preorder_traversal(root):
if root is None:
return

stack = [root]

while stack:
node = stack.pop()

# 1. Visit the current node
print(node.value)

# 2. Push the right child first (if it exists)
if node.right:
stack.append(node.right)

# 3. Push the left child (if it exists)
if node.left:
stack.append(node.left)
```

### Preorder Traversal using Morris Method(Space-Efficient)

```def morris_preorder_traversal(root):
current = root

while current is not None:
if current.left is None:
# 1. Visit the current node
print(current.value)
current = current.right
else:
# Find the rightmost node in the left subtree
predecessor = current.left
while (predecessor.right is not None) and (predecessor.right != current):
predecessor = predecessor.right

if predecessor.right is None:
predecessor.right = current
# 2. Visit the current node
print(current.value)
current = current.left
else:
predecessor.right = None
current = current.right
```

### Applications of Tree Traversal in Data Structure

Tree traversal algorithms have a wide range of applications in computer science and real-world scenarios. Some common applications include:

### To Wrap it up:

In conclusion, Whether you opt for the recursive, iterative (using a stack), or space-efficient Morris traversal method, mastering preorder traversal is essential for efficiently handling binary trees and a wide array of applications in computer science and programming. Understanding the concept and its applications is a valuable asset for developers and problem solvers dealing with tree structures.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription Question 1.

Can Preorder Traversal be Implemented Recursively?

Yes, you can implement preorder traversal using a recursive approach. This involves defining a recursive function that visits the current node and recursively traverses the left and right subtrees. Question 2.

Are There Non-Recursive Methods for Preorder Traversal?

Yes, you can use an iterative approach with a stack data structure to perform preorder traversal without recursion. Another method, known as Morris traversal, is a space-efficient non-recursive technique. Question 3.

What’s the Time Complexity of Preorder Traversal?

The time complexity of preorder traversal is O(n), where ‘n’ is the number of nodes in the binary tree. This is because you need to visit each node exactly once.

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others