- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- Prime Video
- OffCampus Updates
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# 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.

Let’s learn more about Preorder Traversal of Binary Tree along with its working and implementation.

**Methods of Tree Traversal**

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

- Preorder Traversal
- Postorder Traversal
- Inorder Traversal

In this article, we are going to explore more about **Preorder Traversal** of Binary Tree.

**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**

**Working 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.**

**Preorder Traversal using Recursive Method**

**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: # Make the threaded link from predecessor to the current node predecessor.right = current # 2. Visit the current node print(current.value) current = current.left else: # Remove the threaded link predecessor.right = None current = current.right

**Complexity Analysis of Preorder Traversal**

**Time complexity**is O(N), meaning the algorithm's runtime grows linearly with the number of nodes in the tree.

**auxiliary space**complexity is O(1) if we don't consider the function call stack; otherwise, it's O(h), where h represents the tree's height, accounting for the space used by recursive function calls.

**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.

### Prime Course Trailer

### 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