N-ary Tree Postorder Traversal

🏠 ⬅️ ➡️

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:

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

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • 0 <= Node.val <= 104
  • The height of the n-ary tree is less than or equal to 1000.

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, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=256) :: filename_in, filename_out
    type :: node
        real(kind=DP), allocatable :: val(:)
    end type node
    type(node), pointer :: root
    integer :: i, j, k, n, m

    ! read input from file
    write (unit=unit_out, fmt='(A)') 'Enter filename for input:'
    read (unit=unit_in, fmt='(A)') filename_in
    open (newunit=unit_in, file=filename_in, status='old', action='read', &
          access='sequential', form='formatted', iostat=i, iomsg=filename_in)
    if (i /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: can not open file "', trim(filename_in)
        stop 1
    end if
    read (unit=unit_in, fmt=*) n
    allocate (root%val(n))
    do i = 1, n
        read (unit=unit_in, fmt=*) root%val(i)
    end do
    close (unit=unit_in)

    ! solve the problem
    call postorder_traversal(root)

    ! write output to file
    write (unit=unit_out, fmt='(A)') 'Enter filename for output:'
    read (unit=unit_in, fmt='(A)') filename_out
    open (newunit=unit_out, file=filename_out, status='replace', action='write', &
          access='sequential', form='formatted', iostat=i, iomsg=filename_out)
    if (i /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: can not create file "', trim(filename_out)
        stop 1
    end if
    write (unit=unit_out, fmt=*) root%val
    close (unit=unit_out)

contains

    subroutine postorder_traversal(root)
        implicit none
        class(node), intent(inout) :: root
        integer :: i, j, k, n
        logical :: done

        done = .false.
        do while (.not. done)
            select case (size(root%val))
                case (0)
                    done = .true.
                case (1)
                    done = .true.
                case default
                    do i = 1, size(root%val)-1
                        if (allocated(root%val(i)%val)) then
                            call postorder_traversal(root%val(i))
                        end if
                    end do
                    do i = size(root%val), 2, -1
                        if (allocated(root%val(i)%val)) then
                            call postorder_traversal(root%val(i))
                        end if
                    end do
                    done = .true.
            end select
        end do
    end subroutine postorder_traversal

end program main
❌ Compiled
❌ Executed
❌ Correct 
module nary_tree_postorder_traversal
implicit none
private
public :: nary_tree_postorder_traversal

contains

function postorder_traversal(root) result(postorder)
    type(nary_tree_node), pointer, intent(in) :: root
    integer, allocatable :: postorder(:)
    integer :: i, j, k, n
    type(nary_tree_node), pointer :: curr

    ! Count the number of nodes in the tree
    n = 0
    curr => root
    do while (associated(curr))
        n = n + 1
        curr => curr%children
    end do

    ! Allocate the output array
    allocate(postorder(n))

    ! Initialize the output array
    postorder = 0

    ! Traverse the tree in postorder
    curr => root
    i = 1
    do while (associated(curr))
        ! Traverse the current node's children
        j = 1
        do while (associated(curr%children))
            postorder(i) = curr%children%val
            i = i + 1
            curr => curr%children
        end do

        ! Traverse the current node's siblings
        k = 1
        do while (associated(curr%sibling))
            postorder(i) = curr%sibling%val
            i = i + 1
            curr => curr%sibling
        end do

        ! Move to the next node
        curr => curr%parent
    end do
end function postorder_traversal

! A node in an n-ary tree
type nary_tree_node
    integer :: val
    type(nary_tree_node), pointer :: children(:) => null()
    type(nary_tree_node), pointer :: sibling => null()
    type(nary_tree_node), pointer :: parent => null()
end type nary_tree_node

! A root node for an n-ary tree
type nary_tree_root
    type(nary_tree_node), pointer :: root => null()
end type nary_tree_root

! A constructor for an n-ary tree root
function nary_tree_root_constructor(val) result(root)
    integer, intent(in) :: val
    type(nary_tree_root) :: root
    allocate(root%root)
    root%root%val = val
end function nary_tree_root_constructor

! A destructor for an n-ary tree root
subroutine nary_tree_root_destructor(root)
    type(nary_tree_root), intent(inout) :: root
    deallocate(root%root)
end subroutine nary_tree_root_destructor

! A constructor for an n-ary tree node
function nary_tree_node_constructor(val) result(node)
    integer, intent(in) :: val
    type(nary_tree_node) :: node
    node%val = val
end function nary_tree_node_constructor

! A destructor for an n-ary tree node
subroutine nary_tree_node_destructor(node)
    type(nary_tree_node), intent(inout) :: node
    deallocate(node%children)
    deallocate(node%sibling)
    deallocate(node%parent)
end subroutine nary_tree_node_destructor

! A function to add a child to an n-ary tree node
subroutine nary_tree_node_add_child(node, child)
    type(nary_tree_node), intent(inout) :: node
    type(nary_tree_node), intent(in) :: child
    integer :: i

    ! Allocate the children array if necessary
    if (.not. associated(node%children)) then
        allocate(node%children(1))
    else
        allocate(node%children(size(node%children) + 1))
    end if

    ! Add the child to the children array
    do i = size(node%children), 2, -1
        node%children(i) => node%children(i - 1)
    end do
    node%
🌐 Data from online sources 
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

def postorder(root):
    result = []
    if not root:
        return result

    stk = [root]

    while stk:
        current = stk.pop()
        result.append(current.val)

        for child in current.children:
            stk.append(child)

    return result[::-1]

The algorithm for iterative postorder traversal of an n-ary tree is as follows:

  1. Create an empty stack and push the root node onto it.
  2. While the stack is not empty: a. Pop the top node from the stack and add its value to the result list. b. Iterate through the node's children, pushing them onto the stack.
  3. Reverse the result list and return it.

This algorithm ensures a depth-first traversal of the tree, visiting each node's children before the node itself (postorder traversal). By reversing the result list at the end, the desired postorder list is obtained.

🌐 Data from online sources 
struct Node {
    int val;
    vector<Node*> children;
};

vector<int> postorder(Node* root) {
    vector<int> result;
    if (!root) return result;

    stack<Node*> stk;
    stk.push(root);

    while (!stk.empty()) {
        Node* current = stk.top();
        stk.pop();
        result.push_back(current->val);

        for (auto child : current->children)
            stk.push(child);
    }

    reverse(result.begin(), result.end());
    return result;
}

The algorithm for iterative postorder traversal of an n-ary tree is as follows:

  1. Create an empty stack and push the root node onto it.
  2. While the stack is not empty: a. Pop the top node from the stack and add its value to the result list. b. Iterate through the node's children, pushing them onto the stack.
  3. Reverse the result list and return it.

This algorithm ensures a depth-first traversal of the tree, visiting each node's children before the node itself (postorder traversal). By reversing the result list at the end, the desired postorder list is obtained.