Back to: Python Data Structure and Algorithims

🌳 Coding Depth-First Search (DFS) Postorder Traversal in Python

In the previous section, we explored how Postorder Depth-First Search (DFS) works conceptually — visiting the left subtree, then the right subtree, and finally the current node.

Now, let’s turn that understanding into code and walk through how it executes step by step.

🧩 Recap: Postorder Traversal Order

Left → Right → Root

That’s the golden rule of Postorder DFS.
We only append a node’s value after both its left and right children have been completely processed.

🧠 Step 1: Setting Up the Method

We start by defining our method inside the Binary Search Tree (BST) class:

def DFS_postorder(self):
    results = []

    def traverse(node):
        if node.left:
            traverse(node.left)
        if node.right:
            traverse(node.right)
        results.append(node.value)

    traverse(self.root)
    return results

Let’s break this down line by line.

🏗 Step 2: Creating the `results` List

We begin by creating a list called results that will eventually store the traversal order:

results = []

This list will hold the values (not the nodes themselves) in the correct postorder sequence.

🌀 Step 3: Defining the Recursive Function `traverse()`

Inside our DFS_postorder method, we define a nested function named traverse.
This recursive function will:

Visit the left child
Visit the right child
Append the current node’s value

def traverse(node):
    if node.left:
        traverse(node.left)
    if node.right:
        traverse(node.right)
    results.append(node.value)

Notice that this function’s structure perfectly mirrors the Left → Right → Root pattern.

🚀 Step 4: Kicking Things Off with the Root

We initiate traversal with the tree’s root node:

traverse(self.root)

This pushes the first call of traverse() onto the call stack — beginning our recursive exploration.

🧠 Step-by-Step Execution with the Call Stack

Let’s visualize the process using the following binary tree:

        47
       /  \
     21    76
    / \    / \
   18 27  52 82

🪜 Step 1: Start with Root (47)

traverse(47) is added to the call stack.
47 looks left → traverse(21) is added.

🪜 Step 2: Visit 21

21 looks left → traverse(18) is added.

🌿 Step 3: Visit 18

18 has no left or right child.
It appends its value → results = [18].
18 is popped off the call stack.

🧩 Step 4: Back to 21 → Go Right

21 now goes right → traverse(27) is added.
27 has no children, so it appends → results = [18, 27].
27 is popped from the call stack.

Now 21 has processed left and right, so it appends itself →
results = [18, 27, 21].

21 is popped off.

🌲 Step 5: Back to 47 → Go Right

Now 47 looks right → traverse(76) is added to the stack.

🌿 Step 6: Visit 76 → Go Left to 52

76 goes left → traverse(52) is added.
52 appends → results = [18, 27, 21, 52].
52 is popped.

🌿 Step 7: Visit 76 → Go Right to 82

76 goes right → traverse(82) is added.
82 appends → results = [18, 27, 21, 52, 82].
82 is popped.

Now 76 appends → results = [18, 27, 21, 52, 82, 76].

🌳 Step 8: Finish with 47

Finally, 47 appends →
✅ results = [18, 27, 21, 52, 82, 76, 47]

This matches the exact postorder traversal order.

💻 Full Method Implementation

Here’s the complete Python code inside your Binary Search Tree class:

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def DFS_postorder(self):
        results = []

        def traverse(node):
            if node.left:
                traverse(node.left)
            if node.right:
                traverse(node.right)
            results.append(node.value)

        traverse(self.root)
        return results

🧪 Example Execution in VS Code

Suppose we create the same tree:

my_tree = BinarySearchTree()
my_tree.insert(47)
my_tree.insert(21)
my_tree.insert(76)
my_tree.insert(18)
my_tree.insert(27)
my_tree.insert(52)
my_tree.insert(82)

print(my_tree.DFS_postorder())

✅ Output:

[18, 27, 21, 52, 82, 76, 47]

🎯 Key Takeaways

Postorder DFS processes a node after both its subtrees are fully visited.
Perfect for tasks where child nodes must be handled before their parent — like deleting a tree or evaluating expression trees.
Implementation relies on a simple recursive pattern with a clean, intuitive flow.