Depth Order Traversals: Binary Tree

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

Iteration of Preorder Traversal#

1. Push the root to the stack.

2. Is the stack empty?

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

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

5. Push the right, then left children into the stack.

6. End of first iteration.

7. 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->Left-Right"""
    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.²

Iteration of Inorder Traversal#

1. Add the root to the queue.

2. Is the queue empty?

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

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

5. Push the left, then right children to the queue.

6. End of first iteration.

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

1. Check if the current node is empty/null.

2. Traverse the left subtree by recursively calling the post-order method.

3. Traverse the right subtree by recursively calling the post-order method.

4. Display/Act upon on the current node.

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