# Inorder Traversal of Binary Tree ## Introduction to Inorder Traversal

Inorder Traversal of Binary Tree is a versatile technique with applications ranging from organizing data in sorted order to evaluating expressions, parsing code, creating abstract syntax trees, and ensuring the validity of binary trees. Inorder traversal is a fundamental tree traversal algorithm used to visit and process all the nodes of a binary tree. The term “inorder” refers to the specific order in which nodes are visited during this traversal.

## What is Inorder Traversal of Binary Tree?

An “inorder traversal” is a method of visiting or traversing the nodes of a binary tree, a hierarchical data structure. Specifically, it is a depth-first traversal algorithm that follows the left, root, and right order, which is why it is sometimes also called “left-root-right” traversal.

## Inorder Traversal Example ## Visualization of Inorder Traversal

In inorder traversal, you visit the nodes in a specific order:

• Traverse the left subtree in a inorder fashion.
• Then, traverse through the root of the binary tree
• And at the last, Traverse the right subtree in a inorder fashion. ### Consider a binary tree : Performing a inorder traversal on this binary tree involves the following steps:

### Step 4: Repeat these steps to get the final result. ### Pseudocode for Inorder Traversal of Binary Tree

The pseudocode for implementing inorder traversal is as follows:

```inorder(node):
if node is not null:
inorder(node.left)   // Recursively traverse the left subtree
visit(node)          // Visit (or process) the current node
inorder(node.right)  // Recursively traverse the right subtree
```

### Related Banners

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

### Code :

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

def inorderTraversal(node):
if node is not None:
# Recursively traverse the left subtree
inorderTraversal(node.left)
# Visit (or process) the current node
print(node.val)
# Recursively traverse the right subtree
inorderTraversal(node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Perform the inorder traversal
inorderTraversal(root)
```

```4
2
5
1
3
```

### Explanation :

The code performs an inorder traversal of a binary tree using a recursive approach. It starts from the leftmost node, visits the current node, and then moves to the right subtree. The output displays the values of the tree’s nodes in ascending order if it’s a binary search tree (BST), or in a specific hierarchical order based on the tree’s structure.

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

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

def inorderTraversalIterative(root):
stack = []
current = root

while current is not None or stack:
while current is not None:
stack.append(current)
current = current.left  # Traverse the left subtree
current = stack.pop()
print(current.val, end=' ')  # Print the value with a space
current = current.right  # Traverse the right subtree

# Construct your binary tree with different values
root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)

# Perform the inorder traversal
inorderTraversalIterative(root)
```

### Output :

```1 3 6 8 10
```

### Explanation :

The code demonstrates an iterative inorder traversal of a binary tree. Starting from the leftmost node, it visits each node, prints the value, and moves to the right subtree. The output displays the node values in ascending order, reflecting the hierarchical structure of the tree with the provided numerical values.

### Complexity Analysis of Inorder Traversal of Binary Tree

The time and space complexity analysis for inorder traversal of a binary tree can be summarized as follows:

Time Complexity:

• In the worst case, where the binary tree is skewed, the time complexity of both recursive and iterative inorder traversal is O(n), where n is the number of nodes in the tree. This is because you must visit all nodes once.
• In the average and best cases, for balanced binary trees (e.g., binary search trees), the time complexity is O(n) as well because each node is visited exactly once.

Space Complexity:

• Recursive Inorder Traversal: The space complexity for the recursive approach is determined by the maximum depth of the function call stack, which is proportional to the height of the tree. In the worst case, for a skewed tree, the space complexity is O(n). In a balanced tree, it is O(log n) because the maximum stack depth is logarithmic in terms of the number of nodes.
• Iterative Inorder Traversal: The space complexity for the iterative approach using a stack is also determined by the maximum number of elements stored in the stack, which is proportional to the height of the tree. Similar to the recursive approach, it is O(n) in the worst case (skewed tree) and O(log n) in the best case (balanced tree).

### Applications of Inorder Traversal

Following are the applications of Inorder traversal :

### To Wrap it up:

In conclusion, Inorder traversal of Binary tree is a valuable technique for exploring the nodes of a binary tree, providing ordered access to the tree’s elements. Whether you’re searching for specific elements in a binary search tree, printing elements in sorted order, or tackling more complex algorithms, understanding and implementing inorder traversal is a fundamental skill for any computer scientist or programmer working with binary trees. Question 1.

Can Inorder Traversal be Applied to Non-binary Search Trees?

Yes, inorder traversal can be applied to general binary trees. While it doesn’t guarantee sorted order in non-BSTs, it provides a hierarchical order for processing tree elements. Question 2.

What are Practical Applications of Inorder Traversal?

In addition to searching and sorting, inorder traversal is used in expression evaluation, finding the Kth smallest element, and various tree-related algorithms in computer science. Question 3.

Can Inorder Traversal Detect Unbalanced Trees?

Inorder traversal can be used to detect whether a binary tree is balanced by calculating the height of its left and right subtrees and checking their difference. Unbalanced trees tend to have significant height differences.

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