Tree Traversals (Preorder, Inorder and Postorder)#
From the root of a binary tree, traverse deeper before going laterally.
Preorder  Node Left Right
Inorder  Left Node Right
Postorder  Left Right Node
Preorder Traversal (nlr)#
A useful collection type to navigate the nodes traversed is a stack
^{1}.
Iteration of Preorder Traversal
#

Push the root to the stack.

Is the stack empty?

Then pop the stack, and record/output the node name/value as visited.

Check if the node has children. If yes, continue.

Push the right, then left children into the stack.

End of first iteration.

Repeat for the top value in the stack and continue.
This traversal is Time O(n), and Space O(n)
def preorder_print(self, start, traversal):
"""Node>LeftRight"""
if start:
traversal += str(start.value) + ""
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
Inorder Traversal (lnr)#
From the root of a binary tree, traverse laterally before going deeper.
A useful collection type to navigate the nodes traversed is a queue
.^{2}
Iteration of Inorder Traversal#

Add the root to the queue.

Is the queue empty?

Then pop the queue, and record/output the node name/value as visited.

Check if the node has children. If yes, continue.

Push the left, then right children to the queue.

End of first iteration.

Repeat for the top value in the stack and continue.
This traversal is Time O(n), and Space O(n). Assumes maximum efficiency of add and remove operations from the queue.
def inorder_print(self, start, traversal):
"""Left>Node>Right"""
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += str(start.value) + ""
traversal = self.inorder_print(start.right, traversal)
return traversal
Postorder Traversal (lrn)#
From the root traverse to the leaves first then back to the root. This algorithm can be used to delete trees.
Iteration of Postorder Traversal
#

Check if the current node is empty/null.

Traverse the left subtree by recursively calling the postorder method.

Traverse the right subtree by recursively calling the postorder method.

Display/Act upon on the current node.

Repeat until the current node is the root and act upon the root.
def postorder_print(self, start, traversal):
"""Left>Right>Node"""
if start:
traversal = self.postorder_print(start.left, traversal)
traversal = self.postorder_print(start.right, traversal)
traversal += str(start.value) + ""
return traversal
Admittedly, I’m finding this topic challenging to study on my own, however writing down what I understand has always helped that process.
At some point I think it will be useful to return here and put together some cohesive notes for myself and any one else poking around these posts.
Sources:
Binary Tree Algorithms for Technical Interviews  Full Course
Educative: Data Structures and Algorithms  Binary Trees
Preorder Tree Traversal Algorithm in Python
Binary Tree Algorithms for Technical Interviews  Full Course
Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.
How to add footnotes in Markdown?
This is an example of how to create a footnote[^1] in Markdown.
[^1]: A note placed at the bottom of a page of a book or manuscript that comments on or cites a reference for a designated part of the text.

A sequential data structure that can take in data and only returns the last in value. LIFO. ↩︎

A sequential data structure where we can add to the back and pull from the front of the que. See FIFO, LIFO, and Priority Queues ↩︎