Binary Tree Paths

🏠 ⬅️ ➡️

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5] Output: [ "1->2->5 ", "1->3 "]

Example 2:

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

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem: Given the `root` of a binary tree, return all root-to-leaf paths in any order.
    implicit none

    type :: TreeNode
        integer :: val
        type(TreeNode), pointer :: left => null(), right => null()
    end type TreeNode

    type(TreeNode), target :: root
    character(len=:), allocatable :: str

    call solve(root)

contains

    subroutine solve(root)
        ! Solve the problem
        type(TreeNode), intent(inout) :: root
        type(TreeNode), pointer :: curr
        integer :: i

        if (associated(root%left)) then
            call solve(root%left)
        end if
        if (associated(root%right)) then
            call solve(root%right)
        end if

        if (.not. associated(root%left) .and. .not. associated(root%right)) then
            write (str, "(I0)") root%val
            do while (associated(curr))
                write (str, "(A, I0)") trim(str), curr%val
                curr => curr%left
            end do
            print '(A)', trim(str) // " "
        end if

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module binary_tree_paths

implicit none

contains

function binary_tree_paths_helper(root, path) result(paths)

    type(binary_tree_node), pointer, intent(in) :: root
    character(len=:), allocatable :: path
    character(len=:), allocatable :: paths(:)

    if (associated(root)) then
        path = trim(path) // to_string(root%val)
        if (root%left == null() .and. root%right == null()) then
            paths = [path]
        else
            paths = [path]
            paths = [paths, binary_tree_paths_helper(root%left, path // "->" // to_string(root%val))]
            paths = [paths, binary_tree_paths_helper(root%right, path // "->" // to_string(root%val))]
        end if
    else
        paths = [path]
    end if

end function binary_tree_paths_helper

function binary_tree_paths(root) result(paths)

    type(binary_tree_node), pointer, intent(in) :: root
    character(len=:), allocatable :: path
    character(len=:), allocatable :: paths(:)

    path = ""
    paths = binary_tree_paths_helper(root, path)

end function binary_tree_paths

function to_string(val) result(str)

    integer, intent(in) :: val
    character(len=:), allocatable :: str

    write (str, "(i0)") val

end function to_string

end module binary_tree_paths

program test_binary_tree_paths

use binary_tree_paths, only : binary_tree_paths, binary_tree_node
implicit none

type(binary_tree_node), pointer :: root
character(len=:), allocatable :: paths(:)

! Example 1
root = binary_tree_node([1, 2, 3, null(), 5])
paths = binary_tree_paths(root)
call assert(paths == ["1->2->5", "1->3"])

! Example 2
root = binary_tree_node([1])
paths = binary_tree_paths(root)
call assert(paths == ["1"])

contains

subroutine assert(condition)

logical, intent(in) :: condition

if (.not. condition) then
    write (*,*) "Assertion failed"
    stop 1
end if

end subroutine assert

end program test_binary_tree_paths
🌐 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 binary_tree_paths(root: TreeNode):
    if not root:
        return []
    if not root.left and not root.right:
        return [str(root.val)]
    paths = []
    for path in binary_tree_paths(root.left):
        paths.append(str(root.val) + "->" + path)
    for path in binary_tree_paths(root.right):
        paths.append(str(root.val) + "->" + path)
    return paths

The algorithm is a simple recursive algorithm that explores depth-first each node of the binary tree. Initially, if the root is null, it returns an empty result. Next, if it's a leaf node, it returns the node's value as a string. If it's not a leaf node, it iteratively calls the binary_tree_paths() function for the left child and then the right child, appending the current node's value and a " -> " separator at the beginning of each path. Finally, it aggregates and returns all the resulting paths of the recursive calls. The language-specific implementations are all very similar, with only slight syntax adjustments across languages.

🌐 Data from online sources 
#include <vector>
#include <string>

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<std::string> binaryTreePaths(TreeNode* root) {
    std::vector<std::string> paths;
    if (!root)
        return paths;
    if (!root->left && !root->right) {
        paths.push_back(std::to_string(root->val));
        return paths;
    }
    for (const std::string &path : binaryTreePaths(root->left)) {
      paths.push_back(std::to_string(root->val) + "->" + path);
    }
    for (const std::string &path : binaryTreePaths(root->right)) {
      paths.push_back(std::to_string(root->val) + "->" + path);
    }
    return paths;
}

The algorithm is a simple recursive algorithm that explores depth-first each node of the binary tree. Initially, if the root is null, it returns an empty result. Next, if it's a leaf node, it returns the node's value as a string. If it's not a leaf node, it iteratively calls the binary_tree_paths() function for the left child and then the right child, appending the current node's value and a " -> " separator at the beginning of each path. Finally, it aggregates and returns all the resulting paths of the recursive calls. The language-specific implementations are all very similar, with only slight syntax adjustments across languages.