N-ary Tree Preorder Traversal

🏠 ⬅️ ➡️

Given the root of an n-ary tree, return the preorder 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: [1,3,5,6,2,4]

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: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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=*), parameter :: filename_in = "narytree.txt"
    character(len=*), parameter :: filename_out = "preordertraversal.txt"
    type :: node
        real(kind=DP) :: val
        class(*), pointer :: left => null(), right => null()
    end type
    type(node), pointer :: root => null()
    integer :: i, j, k, l, m, n
    logical :: eof
    real(kind=DP) :: x

    ! Read the input file
    open(newunit=unit_in, file=filename_in, status='old', action='read', &
         form='formatted', access='sequential', position='rewind', &
         iomsg=i, iostat=j)
    if (j /= 0) then
        write(unit=error_unit, fmt='(A,I0,A)') 'Error: Can not open file ', j, ' for reading.'
        stop 1
    end if
    read(unit=unit_in, fmt=*, iomsg=k, iostat=l) root
    close(unit=unit_in)
    if (k /= '') then
        write(unit=error_unit, fmt='(A,A)') 'Error: Reading from file ', trim(k), ' failed.'
        stop 2
    end if
    if (l /= 0) then
        write(unit=error_unit, fmt='(A,I0,A)') 'Error: Reading from file ', l, ' failed.'
        stop 3
    end if

    ! Print the preorder traversal of the nodes' values
    call print_preorder_traversal(root)

contains

    subroutine print_preorder_traversal(root)
        implicit none
        class(node), pointer, intent(in) :: root
        logical :: first
        first = .true.
        do while (associated(root))
            if (.not.first) then
                write(unit=unit_out, fmt='(A)', advance='no') ','
            else
                first = .false.
            end if
            write(unit=unit_out, fmt='(ES24.16)') root%val
            call print_preorder_traversal(root%left)
            call print_preorder_traversal(root%right)
        end do
    end subroutine print_preorder_traversal

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

contains

function preorder_traversal(root) result(preorder)
    ! Return the preorder traversal of the n-ary tree root
    !
    ! Args:
    !     root: The root of the n-ary tree
    !
    ! Returns:
    !     preorder: The preorder traversal of the n-ary tree
    !
    ! Example:
    !     root = [1,null,3,2,4,null,5,6]
    !     preorder = [1,3,5,6,2,4]
    !
    !     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]
    !     preorder = [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
    !
    ! 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.

    type(nary_node), pointer, intent(in) :: root
    type(nary_node), pointer :: current
    integer :: i
    integer, allocatable :: preorder(:)

    ! Allocate memory for the preorder traversal
    allocate(preorder(size(root%children)))

    ! Initialize the current node to the root
    current => root

    ! Iterate through the nodes in the preorder
    do i = 1, size(root%children)
        ! Add the current node's value to the preorder
        preorder(i) = current%val

        ! If the current node has children, add them to the preorder
        if (associated(current%children)) then
            preorder(i+1:) = preorder(i+1:) // current%children
        end if

        ! Move to the next node
        current => current%next
    end do

end function preorder_traversal

end module nary_tree_preorder_traversal

module nary_node
implicit none
private
public :: nary_node

type :: nary_node
    integer :: val
    type(nary_node), pointer, dimension(:) :: children
    type(nary_node), pointer :: next
end type nary_node

end module nary_node

program main
    use nary_tree_preorder_traversal
    use nary_node
    implicit none
    integer, parameter :: n = 10
    integer, parameter :: m = 1000
    integer :: i, j
    type(nary_node), pointer :: root
    integer, allocatable :: preorder(:)

    ! Create a root node
    allocate(root)
    root%val = 1

    ! Create a list of children for the root node
    allocate(root%children(n))
    do i = 1, n
        allocate(root%children(i)%children(m))
        do j = 1, m
            root%children(i)%children(j)%val = i*j
        end do
    end do

    ! Print the preorder traversal of the n-ary tree
    preorder = preorder_traversal(root)
    do i = 1, size(preorder)
        write (*,*) preorder(i)
    end do

end program main
🌐 Data from online sources 
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

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

    while nodes:
        current = nodes.pop()
        result.append(current.val)
        nodes.extend(reversed(current.children))
    return result

The problem asks for an iterative solution, although a recursive solution would be trivial. Therefore, this solution uses a stack data structure to perform the preorder traversal of the n-ary tree.

  1. Initialize an empty list called result to store the traversed node values.
  2. If root is null, return the empty result.
  3. Initialize a stack called nodes and push root onto the stack.
  4. While the stack is not empty, perform the following steps: a. Pop the top node from the stack and store it in a variable called current. b. Add current's value to the result. c. Reverse iterate through current's children, pushing them onto the stack.
  5. Once the stack is empty, return the result.

The algorithm's time complexity is O(n), where n is the number of nodes in the tree. This is because each node gets pushed onto and popped from the stack exactly once. The space complexity is also O(n), as at worst, the stack will store all the nodes in the tree.

🌐 Data from online sources 
#include <vector>

class Node {
public:
    int val;
    std::vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, std::vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

vector<int> preorder(Node* root) {
    vector<int> result;
    if (root == nullptr) return result;
    stack<Node*> nodes;
    nodes.push(root);

    while (!nodes.empty()) {
        Node* current = nodes.top();
        nodes.pop();
        result.push_back(current->val);
        for (int i = current->children.size() - 1; i >= 0; i--) {
            nodes.push(current->children[i]);
        }
    }
    return result;
}

The problem asks for an iterative solution, although a recursive solution would be trivial. Therefore, this solution uses a stack data structure to perform the preorder traversal of the n-ary tree.

  1. Initialize an empty list called result to store the traversed node values.
  2. If root is null, return the empty result.
  3. Initialize a stack called nodes and push root onto the stack.
  4. While the stack is not empty, perform the following steps: a. Pop the top node from the stack and store it in a variable called current. b. Add current's value to the result. c. Reverse iterate through current's children, pushing them onto the stack.
  5. Once the stack is empty, return the result.

The algorithm's time complexity is O(n), where n is the number of nodes in the tree. This is because each node gets pushed onto and popped from the stack exactly once. The space complexity is also O(n), as at worst, the stack will store all the nodes in the tree.