HomeOur TeamContact
Binary Trees
Inorder Tree Traversal with No Recursion
Nisar
September 08, 2022
1 min

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}Inorder Tree Traversal with No Recursion

This function traverses a binary tree iteratively using the in-order tree-traversal algorithm. The Traversal should not use recursion.

Sample Input

```tree =    1
/     \
2       3
/       /   \
4       6     7
\
9
```

Sample Output

```// The input callback will have been called in the following order:
callback(4)
callback(9)
callback(2)
callback(1)
callback(6)
callback(3)
callback(7)
```

```# O(n) time | O(1) space
DEFINE FUNCTION iterativeInOrderTraversal(tree, callback):
SET previousNode TO None
SET currentNode TO tree
WHILE currentNode is not None:
IF previousNode is None or previousNode EQUALS currentNode.parent:
IF currentNode.left is not None:
SET nextNode TO currentNode.left
ELSE:
callback(currentNode)
SET nextNode TO currentNode.right IF currentNode.right is not None else currentNode.parent
ELSEIF previousNode EQUALS currentNode.left:
callback(currentNode)
SET nextNode TO currentNode.right IF currentNode.right is not None else currentNode.parent
ELSE:
SET nextNode TO currentNode.parent
SET previousNode TO currentNode
SET currentNode TO nextNode
```

## Tags

#Difficulty Very Hard#Algorithm
Previous Article
Heap Sort

Heap Sort
January 31, 2022
1 min