Search in a Binary Search Tree

🏠 ⬅️ ➡️

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5 Output: []

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • 1 <= Node.val <= 107
  • root is a binary search tree.
  • 1 <= val <= 107
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, iostat_end
    implicit none
    type(node), pointer :: root
    integer :: val
    integer :: stat

    call get_arguments(root, val)

    if (associated(root)) then
        write (unit=error_unit, fmt='(*(g0))') 'Root: ', root%value
        write (unit=error_unit, fmt='(*(g0))') 'Val: ', val
        write (unit=error_unit, fmt='(*(g0))') 'Result: ', find_node(root, val)
    else
        write (unit=error_unit, fmt='(*(g0))') 'No result found.'
    end if

contains

    function find_node(root, val) result(result)
        class(node), pointer, intent(in) :: root
        integer, intent(in) :: val
        class(node), pointer :: result

        if (.not. associated(root)) then
            nullify(result)
            return
        end if

        if (root%value == val) then
            result => root
        else if (val < root%value) then
            result => find_node(root%left, val)
        else
            result => find_node(root%right, val)
        end if
    end function find_node

    subroutine get_arguments(root, val)
        type(node), pointer :: root
        integer, intent(out) :: val
        character(len=:), allocatable :: line
        integer :: ios

        read (unit=input_unit, fmt='(A)', iostat=ios) line
        if (ios /= 0) then
            if (ios /= iostat_end) then
                write (unit=error_unit, fmt='(*(g0))') 'Error reading input.'
                stop 1
            end if
            return
        end if

        allocate (character(len=len(line)) :: line)
        line = adjustl(line)
        read (unit=line, fmt=*, iostat=ios) root, val
        if (ios /= 0) then
            write (unit=error_unit, fmt='(*(g0))') 'Error parsing input.'
            stop 1
        end if
    end subroutine get_arguments

    type, public :: node
        integer :: value
        class(node), pointer :: left => null(), right => null()
    end type node

end program main
❌ Compiled
❌ Executed
❌ Correct 
module bst_search

implicit none

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

contains

type(bst_node), pointer function search(root, val) result(subtree)
    type(bst_node), pointer :: root
    integer :: val

    if (associated(root)) then
        if (root%val == val) then
            subtree => root
        else if (val < root%val) then
            subtree => search(root%left, val)
        else
            subtree => search(root%right, val)
        end if
    end if
end function search

end module bst_search

program test_bst_search
    use bst_search
    implicit none

    type(bst_node), pointer :: root
    integer :: val

    ! Example 1
    root => bst_node(val=4, left=>bst_node(val=2, left=>bst_node(val=1), right=>bst_node(val=3)), right=>bst_node(val=7))
    val = 2
    write (*,*) 'Example 1: '
    call print_subtree(search(root, val))

    ! Example 2
    root => bst_node(val=4, left=>bst_node(val=2, left=>bst_node(val=1), right=>bst_node(val=3)), right=>bst_node(val=7))
    val = 5
    write (*,*) 'Example 2: '
    call print_subtree(search(root, val))

contains

subroutine print_subtree(root)
    type(bst_node), pointer :: root

    if (associated(root)) then
        write (*,*) root%val
        call print_subtree(root%left)
        call print_subtree(root%right)
    end if
end subroutine print_subtree

end program test_bst_search
🌐 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 searchBST(root: TreeNode, val: int) -> TreeNode:
    if not root or root.val == val:
        return root
    return searchBST(root.right, val) if root.val < val else searchBST(root.left, val)

We use a recursive search function for searching the BST. The basic logic is as follows:
  1. Check if the current node is null or its value equals the target value. If so, return the node itself.
  2. If the target value is greater than the current node's value, search the right child.
  3. If the target value is less than the current node's value, search the left child.

In all four programming languages, the implementation is pretty much the same:

  1. Define a TreeNode structure/class with value, left child, and right child properties.
  2. Apply the algorithm logic in the searchBST function.
🌐 Data from online sources 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val)
        return root;
    return (root->val < val) ? searchBST(root->right, val) : searchBST(root->left, val);
}

We use a recursive search function for searching the BST. The basic logic is as follows: 1. Check if the current node is null or its value equals the target value. If so, return the node itself. 2. If the target value is greater than the current node's value, search the right child. 3. If the target value is less than the current node's value, search the left child.

In all four programming languages, the implementation is pretty much the same:

  1. Define a TreeNode structure/class with value, left child, and right child properties.
  2. Apply the algorithm logic in the searchBST function.