Binary Tree Inorder Traversal

šŸ  ā¬…ļø āž”ļø

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

Example 1:

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

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 :: n = 3
    type(tree_node), allocatable :: roots(:)[:]
    integer :: i

    allocate(roots(n)[*])

    ! Example 1
    allocate(roots(1)[1])
    allocate(roots(1)[1]%left, source=tree_node(-1))
    allocate(roots(1)[1]%right, source=tree_node(2))
    call print_inorder(roots(1)[1])
    deallocate(roots(1)[1])

    ! Example 2
    allocate(roots(1)[1])
    allocate(roots(1)[1]%left, source=tree_node(-1))
    allocate(roots(1)[1]%right, source=tree_node(-1))
    call print_inorder(roots(1)[1])
    deallocate(roots(1)[1])

    ! Example 3
    allocate(roots(1)[1])
    allocate(roots(1)[1]%left, source=tree_node(1))
    allocate(roots(1)[1]%right, source=tree_node(2))
    call print_inorder(roots(1)[1])
    deallocate(roots(1)[1])

contains

    subroutine print_inorder(root)
        type(tree_node), intent(in) :: root
        if (associated(root%left)) then
            call print_inorder(root%left)
        end if
        write (unit=error_unit, fmt='(*(g0,1x))') root%value
        if (associated(root%right)) then
            call print_inorder(root%right)
        end if
    end subroutine print_inorder

end program main

type :: tree_node
    real(kind=DP) :: value
    class(tree_node), pointer :: left => null()
    class(tree_node), pointer :: right => null()
end type tree_node
āŒ Compiled
āŒ Executed
āŒ Correct 
module binary_tree_inorder_traversal
implicit none
private
public :: inorder_traversal

contains

function inorder_traversal(root) result(values)
    type(node), pointer, intent(in) :: root
    integer, allocatable :: values(:)

    integer :: i, n
    type(node), pointer :: current

    ! Find the number of nodes in the tree
    n = 0
    current => root
    do while (associated(current))
        n = n + 1
        current => current%left
    end do

    ! Allocate an array to store the values
    allocate(values(n))

    ! Perform the inorder traversal
    i = 1
    current => root
    do while (associated(current))
        if (associated(current%left)) then
            current => current%left
            do while (associated(current))
                values(i) = current%val
                i = i + 1
                current => current%right
            end do
        end if
        values(i) = current%val
        i = i + 1
        current => current%right
    end do

end function inorder_traversal

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

end module binary_tree_inorder_traversal

program test
use binary_tree_inorder_traversal
implicit none

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

! Example 1
root => node(1, null(), null())
root%left => node(2, null(), null())
root%right => node(3, null(), null())
values = inorder_traversal(root)
write (*,*) values

! Example 2
root => null()
values = inorder_traversal(root)
write (*,*) values

! Example 3
root => node(1, null(), null())
values = inorder_traversal(root)
write (*,*) values

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 inorderTraversalHelper(root, result):
    if not root:
        return
    inorderTraversalHelper(root.left, result)
    result.append(root.val)
    inorderTraversalHelper(root.right, result)

def inorderTraversal(root):
    result = []
    inorderTraversalHelper(root, result)
    return result

The algorithm simply performs an inorder traversal on the given binary tree. An inorder traversal goes as follows:

  1. Traverse the left subtree, and call the function recursively for the left child.
  2. Visit the root.
  3. Traverse the right subtree, and call the function recursively for the right child.

This process is implemented by defining a helper function (inorderTraversalHelper) that takes a node and a result list (or vector in C++), and appends the node's value to the result list according to the inorder traversal order. The main inorderTraversal function initializes the result list and calls the helper function with the root of the tree. At the end, inorderTraversal returns the result list containing the values of the nodes in inorder traversal order.

šŸŒ Data from online sources 
#include<vector>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
};

void inorderTraversalHelper(TreeNode* root, vector<int>& result) {
    if (!root) return;
    inorderTraversalHelper(root->left, result);
    result.push_back(root->val);
    inorderTraversalHelper(root->right, result);
}

vector<int> inorderTraversal(TreeNode* root){
    vector<int> result;
    inorderTraversalHelper(root, result);
    return result;
}

The algorithm simply performs an inorder traversal on the given binary tree. An inorder traversal goes as follows:

  1. Traverse the left subtree, and call the function recursively for the left child.
  2. Visit the root.
  3. Traverse the right subtree, and call the function recursively for the right child.

This process is implemented by defining a helper function (inorderTraversalHelper) that takes a node and a result list (or vector in C++), and appends the node's value to the result list according to the inorder traversal order. The main inorderTraversal function initializes the result list and calls the helper function with the root of the tree. At the end, inorderTraversal returns the result list containing the values of the nodes in inorder traversal order.