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

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)

Pseudo Code

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

Nisar

Related Posts

Heap Sort
January 31, 2022
1 min
© 2022, All Rights Reserved.

Quick Links

Advertise with usAbout UsContact Us

Social Media