Post-order Traversal

#include <bits/stdc++.h> // Includes common standard libraries (like iostream)
#include "BinaryTree.h"  // Assumed to contain Node class and buildTree function definitions

using namespace std;     // Uses the standard namespace

// Function to perform Post-Order Traversal recursively
// (Left Subtree -> Right Subtree -> Root)
void postOrderRecursive(Node* root) {
    // Base Case: If the current node is NULL, stop recursion for this branch.
    if(root == NULL) {
        return;
    }

    // 1. Recur for Left Subtree: Call the function for the left child.
    postOrderRecursive(root->left);

    // 2. Recur for Right Subtree: Call the function for the right child.
    postOrderRecursive(root->right);

    // 3. Process the Root: Print the data of the current node.
    cout << root->data << " ";
}

int main() {
    Node* root = NULL; // Initialize the root of the tree to NULL

    // Creating a tree: This function is assumed to be defined in "BinaryTree.h"
    // It typically takes input in a pre-order fashion (e.g., 1 3 7 -1 -1 11 -1 -1 5 17 -1 -1 -1)
    root = buildTree(root);

    cout << "\nPost Order Traversal : " << endl; // Output label
    postOrderRecursive(root);                   // Perform and print the post-order traversal
    cout << endl; // Add a newline for better formatting after traversal output

    return 0; // End of the program
}

/*
Example INPUT for buildTree function (for reference):
1 3 7 -1 -1 11 -1 -1 5 17 -1 -1 -1

This input creates a tree structure like this:
        1
       / \
      3   5
     / \   \
    7  11  17

Post-Order Traversal output for this tree will be: 7 11 3 17 5 1
*/

1. Binary Tree Node Structure

• A Node in a Binary Tree typically consists of:
  • data: The value stored in the node.
  • left: A pointer to the left child node.
  • right: A pointer to the right child node.

2. Post-Order Traversal

• Definition: A way to visit (or “traverse”) all nodes in a Binary Tree. In Post-order traversal, the order of visiting is:

  1. Left Subtree (Recursively traverse the left child)
  2. Right Subtree (Recursively traverse the right child)
  3. Root (Process the current node)

• Recursive Algorithm:

  • Base Case: If the current node is NULL (meaning you’ve reached beyond a leaf or an empty tree), simply return.
  • Recursive Step:
    1. Make a recursive call to postOrderRecursive for the root->left child.
    2. Make a recursive call to postOrderRecursive for the root->right child.
    3. Process the data of the current root node (e.g., print it).

• Use Cases:

  • Deleting a Tree: Ensures that child nodes are deleted before their parent, preventing dangling pointers.
  • Representing expressions in postfix notation (Reverse Polish Notation).
  • Calculating space required by files and directories (where parent size depends on children sizes).

3. Complexity Analysis

• Time Complexity: O(N)
  • Each node in the tree is visited exactly once.
• Space Complexity: O(H)
  • This is due to the recursion call stack. H is the height of the tree.
  • In the worst case (a skewed tree, resembling a linked list), H can be N, leading to O(N) space.
  • In the best case (a perfectly balanced tree), H is log N, leading to O(log N) space.

---