Binary Tree Postorder Traversal

🏠 ⬅️ ➡️

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3] Output: [3,2,1]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Constraints:

  • The number of the nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, output_unit
    implicit none
    integer, parameter :: n = 5
    type(node), allocatable :: roots(:)
    integer :: i

    allocate(roots(n))

    ! Example 1
    call init_node(roots(1), 1, null(), null())
    call init_node(roots(2), 2, roots(1), null())
    call init_node(roots(3), 3, null(), roots(2))
    call init_node(roots(4), 4, roots(3), null())
    call init_node(roots(5), 5, roots(4), null())
    write (output_unit, '(*(g0,:," "))') 'Example 1:'
    call print_postorder(roots(5))
    deallocate(roots)

    ! Example 2
    allocate(roots(1))
    call init_node(roots(1), 1, null(), null())
    write (output_unit, '(*(g0,:," "))') 'Example 2:'
    call print_postorder(roots(1))
    deallocate(roots)

    ! Example 3
    allocate(roots(1))
    call init_node(roots(1), 1, null(), null())
    write (output_unit, '(*(g0,:," "))') 'Example 3:'
    call print_postorder(roots(1))
    deallocate(roots)

contains

    subroutine init_node(this, val, left, right)
        class(node), intent(out) :: this
        integer, intent(in) :: val
        class(node), intent(in), optional :: left, right

        this%val = val
        if (present(left)) then
            this%left => left
        else
            this%left => null()
        end if
        if (present(right)) then
            this%right => right
        else
            this%right => null()
        end if
    end subroutine init_node

    recursive subroutine print_postorder(root)
        class(node), intent(in) :: root

        if (.not. associated(root%left)) then
            if (.not. associated(root%right)) then
                write (output_unit, '(i0)') root%val
            else
                call print_postorder(root%right)
                write (output_unit, '(i0)') root%val
            end if
        else
            call print_postorder(root%left)
            if (.not. associated(root%right)) then
                write (output_unit, '(i0)') root%val
            else
                call print_postorder(root%right)
                write (output_unit, '(i0)') root%val
            end if
        end if
    end subroutine print_postorder

end program main

type node
    integer :: val
    class(node), pointer :: left => null(), right => null()
end type node
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTreePostorderTraversal
    implicit none
    private
    public :: binary_tree_postorder_traversal
contains
    subroutine binary_tree_postorder_traversal(root, values)
        type(Node), pointer, intent(in) :: root
        integer, allocatable, intent(out) :: values(:)

        integer :: i, n

        ! Allocate memory for the values array
        n = size(values)
        allocate(values(n))

        ! Postorder traversal
        call postorder_traversal(root, values, 1, n)
    end subroutine binary_tree_postorder_traversal

    recursive subroutine postorder_traversal(root, values, i, n)
        type(Node), pointer, intent(in) :: root
        integer, allocatable, intent(inout) :: values(:)
        integer, intent(in) :: i, n

        if (associated(root)) then
            ! Recursively traverse the left subtree
            call postorder_traversal(root%left, values, i, n)

            ! Recursively traverse the right subtree
            call postorder_traversal(root%right, values, i, n)

            ! Assign the current node's value to the next available position in the values array
            values(i) = root%val
            i = i + 1
        end if
    end subroutine postorder_traversal

    type Node
        integer :: val
        type(Node), pointer :: left
        type(Node), pointer :: right
    end type Node
end module BinaryTreePostorderTraversal

program test_binary_tree_postorder_traversal
    use BinaryTreePostorderTraversal
    implicit none

    type(Node), pointer :: root
    integer, allocatable :: values(:)

    ! Example 1
    root = Node(1, Node(2, Node(4, Node(8, Node(16, Node(32, Node(64, Node(128, Node(256, Node(512, Node(1024, Node(2048, Node(4096, Node(8192, Node(16384, Node(32768, Node(65536, Node(131072, Node(262144, Node(524288, Node(1048576, Node(2097152, Node(4194304, Node(8388608, Node(16777216, Node(33554432, Node(67108864, Node(134217728, Node(268435456, Node(536870912, Node(1073741824, Node(2147483648, Node(4294967296, Node(8589934592, Node(17179869184, Node(34359738368, Node(68719476736, Node(137438953472, Node(274877906944, Node(549755813888, Node(1199438665216, Node(2398912007424, Node(4797824014848, Node(9595648029792, Node(19191296059584, Node(38382592119168, Node(76765184238336, Node(153530368476736, Node(307061734943488, Node(614123479886976, Node(1228246959773952, Node(24
🌐 Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root):
    if not root:
        return []

    result = []
    s = [root]
    while s:
        current = s.pop()
        result.insert(0, current.val)
        if current.left:
            s.append(current.left)
        if current.right:
            s.append(current.right)

    return result

The idea of the algorithm is using a stack. Initially, the root node is pushed to the stack. Next, we enter a loop that ends when the stack is empty. In each iteration, we pop a node from the stack, and insert its value at the beginning of the result list (to ensure the correct order for the postorder traversal), then, push its left child, and then its right child to the stack (if they are not null). In the end, we return the result list. The algorithm is non-recursive which makes it easier to understand for some. Since the result list will store the output in reversed order, this iterative version avoids the necessity of reversing the final output.

🌐 Data from online sources 
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> s;

    if (!root) return result;

    s.push(root);
    while (!s.empty()) {
        TreeNode *current = s.top();
        s.pop();
        result.insert(result.begin(), current->val);
        if (current->left) s.push(current->left);
        if (current->right) s.push(current->right);
    }

    return result;
}

The idea of the algorithm is using a stack. Initially, the root node is pushed to the stack. Next, we enter a loop that ends when the stack is empty. In each iteration, we pop a node from the stack, and insert its value at the beginning of the result list (to ensure the correct order for the postorder traversal), then, push its left child, and then its right child to the stack (if they are not null). In the end, we return the result list. The algorithm is non-recursive which makes it easier to understand for some. Since the result list will store the output in reversed order, this iterative version avoids the necessity of reversing the final output.