Binary Tree Preorder Traversal

🏠 ⬅️ ➡️

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

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

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

Constraints:

  • The number of 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, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=*), parameter :: filename_in = "example_input.txt"
    character(len=*), parameter :: filename_out = "example_output.txt"
    type :: node
        real(kind=DP) :: val
        type(node), pointer :: left => null(), right => null()
    end type
    type(node), pointer :: root
    integer :: iostat
    logical :: exists

    ! Read input from file
    open(newunit=unit_in, file=filename_in, status="old", action="read", &
         form="formatted", access="sequential", iostat=iostat, &
         position="rewind")
    if (iostat /= 0) then
        write(unit=error_unit, fmt="(A)") "Error: cannot open input file."
        stop 1
    end if
    exists = .true.
    call read_tree(unit_in, root, exists)
    close(unit=unit_in)

    ! Output preorder traversal
    write(unit=unit_out, fmt="(*(G0))") preorder_traversal(root)

    ! Write output to file
    open(newunit=unit_out, file=filename_out, status="replace", action="write", &
         form="formatted", access="sequential", iostat=iostat, &
         position="rewind")
    if (iostat /= 0) then
        write(unit=error_unit, fmt="(A)") "Error: cannot open output file."
        stop 1
    end if
    call write_preorder_traversal(unit_out, root)
    close(unit=unit_out)

contains

    function preorder_traversal(root) result(values)
        implicit none
        class(node), intent(in) :: root
        real(kind=DP), allocatable :: values(:)
        allocate(values(size(root)))
        values = preorder_traversal_recursive(root)
    end function

    recursive function preorder_traversal_recursive(root) result(values)
        implicit none
        class(node), intent(in) :: root
        real(kind=DP), allocatable :: values(:)
        if (.not. associated(root)) then
            allocate(values(0))
            return
        end if
        allocate(values(size(root)+1))
        values(1) = root%val
        values(2:) = preorder_traversal_recursive(root%left)
        values(size(values)-1:) = preorder_traversal_recursive(root%right)
    end function

    subroutine write_preorder_traversal(unit, root)
        implicit none
        integer, value :: unit
        class(node), intent(in) :: root
        if (.not. associated(root)) then
            return
        end if
        write(unit=unit, fmt="(G0)") root%val
        call write_preorder_traversal(unit, root%left)
        call write_preorder_traversal(unit, root%right)
    end subroutine

    subroutine read_tree(unit, root, exists)
        implicit none
        integer, value :: unit
        class(node), pointer :: root
        logical, intent(out) :: exists
        real(kind=DP) :: val
        exists = .false.
        read(unit=unit, fmt=*, iostat=iostat) val
        if (iostat == 0) then
            exists = .true.
            allocate(root)
            root%val = val
            call read_tree(unit, root%left, exists)
            call read_tree(unit, root%right, exists)
        end if
    end subroutine

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

type :: binary_tree_node
    integer :: val
    type(binary_tree_node), pointer :: left
    type(binary_tree_node), pointer :: right
end type binary_tree_node

contains

function binary_tree_preorder_traversal(root) result(preorder)
    type(binary_tree_node), pointer, intent(in) :: root
    integer, allocatable :: preorder(:)
    integer :: i, n

    ! Count the number of nodes in the tree
    n = count_nodes(root)

    ! Allocate an array to store the preorder traversal
    allocate(preorder(n))

    ! Perform the preorder traversal
    i = 1
    call preorder_traversal(root, preorder, i)

end function binary_tree_preorder_traversal

recursive subroutine preorder_traversal(root, preorder, i)
    type(binary_tree_node), pointer, intent(in) :: root
    integer, allocatable, intent(inout) :: preorder(:)
    integer, intent(inout) :: i

    ! Base case: if the root is null, return
    if (.not. associated(root)) return

    ! Store the root's value in the preorder array
    preorder(i) = root%val
    i = i + 1

    ! Recursively traverse the left subtree
    call preorder_traversal(root%left, preorder, i)

    ! Recursively traverse the right subtree
    call preorder_traversal(root%right, preorder, i)

end subroutine preorder_traversal

recursive function count_nodes(root) result(n)
    type(binary_tree_node), pointer, intent(in) :: root
    integer :: n

    ! Base case: if the root is null, return 0
    if (.not. associated(root)) then
        n = 0
        return
    end if

    ! Recursively count the number of nodes in the left and right subtrees
    n = 1 + count_nodes(root%left) + count_nodes(root%right)

end function count_nodes

end module binary_tree_preorder_traversal

program test
    use binary_tree_preorder_traversal
    implicit none

    ! Test case 1: Empty tree
    type(binary_tree_node), pointer :: root
    integer, allocatable :: preorder(:)

    root => null()
    preorder = binary_tree_preorder_traversal(root)
    write(*,*) preorder

    ! Test case 2: Single node
    root => binary_tree_node(1, null(), null())
    preorder = binary_tree_preorder_traversal(root)
    write(*,*) preorder

    ! Test case 3: Binary tree
    root => binary_tree_node(1, &
        binary_tree_node(2, null(), null()), &
        binary_tree_node(3, null(), null()))
    preorder = binary_tree_preorder_traversal(root)
    write(*,*) preorder

end program test
🌐 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 preorderTraversal(root):
    if root is None:
        return []

    return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)

The algorithm performs a preorder traversal of the binary tree, which involves visiting the root node, then the left subtree, and finally the right subtree. This is a simple recursive algorithm:

  1. If the binary tree is empty (i.e., the root is null), return an empty list.

  2. For a non-empty binary tree with root r, left subtree left, and right subtree right, return a list containing:

    • r.val
    • The elements of the list returned by the call preorderTraversal(left).
    • The elements of the list returned by the call preorderTraversal(right).

Note that this algorithm can be implemented in each language using similar concepts, but the syntax for concatenating lists in each language may differ.

🌐 Data from online sources 
#include<vector>

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

std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    result.push_back(root->val);
    std::vector<int> left = preorderTraversal(root->left);
    std::vector<int> right = preorderTraversal(root->right);

    result.insert(result.end(), left.begin(), left.end());
    result.insert(result.end(), right.begin(), right.end());

    return result;
}

The algorithm performs a preorder traversal of the binary tree, which involves visiting the root node, then the left subtree, and finally the right subtree. This is a simple recursive algorithm:

  1. If the binary tree is empty (i.e., the root is null), return an empty list.

  2. For a non-empty binary tree with root r, left subtree left, and right subtree right, return a list containing:

    • r.val
    • The elements of the list returned by the call preorderTraversal(left).
    • The elements of the list returned by the call preorderTraversal(right).

Note that this algorithm can be implemented in each language using similar concepts, but the syntax for concatenating lists in each language may differ.