Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3] Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49] Output: 1
Constraints:
[2, 100].0 <= Node.val <= 105Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
program main
use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
implicit none
integer, parameter :: n = 2
real(DP), dimension(n) :: x
real(DP) :: y
integer :: i
! Examples
x(1) = 4._DP
x(2) = 2._DP
call test_case(x, 1._DP)
x(1) = 1._DP
x(2) = 48._DP
call test_case(x, 1._DP)
contains
subroutine test_case(x, expected)
real(DP), intent(in) :: x(:)
real(DP), intent(in) :: expected
real(DP) :: result
result = min_diff(x)
write (unit=error_unit, fmt='(A, F10.3, A, F10.3, A)') &
'Test case: ', x, ' -> ', result, ' (expected: ', expected, ')'
end subroutine test_case
end program main
function min_diff(root) result(res)
type(node), pointer, intent(in) :: root
real(DP) :: res
real(DP) :: diff
if (.not. associated(root)) then
res = -1._DP
return
end if
diff = abs(root%val - root%left%val)
res = min(res, diff)
res = min(res, min_diff(root%left))
res = min(res, min_diff(root%right))
end function min_diff
type node
real(DP) :: val
type(node), pointer :: left
type(node), pointer :: right
end type nodetemp.f95:33:15:
33 | type(node), pointer, intent(in) :: root
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:34:9:
34 | real(DP) :: res
| 1
Error: Parameter ‘dp’ at (1) has not been declared or is a variable, which does not reduce to a constant expression
temp.f95:35:9:
35 | real(DP) :: diff
| 1
Error: Parameter ‘dp’ at (1) has not been declared or is a variable, which does not reduce to a constant expression
temp.f95:38:20:
38 | res = -1._DP
| 1
Error: Missing kind-parameter at (1)
temp.f95:42:21:
42 | diff = abs(root%val - root%left%val)
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:44:34:
44 | res = min(res, min_diff(root%left))
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:45:34:
45 | res = min(res, min_diff(root%right))
| 1
Error: Symbol ‘root’ at (1) has no IMPLICIT type
temp.f95:1:12:
1 | program main
| 1
......
48 | type node
| 2
Error: Two main PROGRAMs at (1) and (2)
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/11/../../../x86_64-linux-gnu/Scrt1.o: in function `_start': (.text+0x1b): undefined reference to `main' collect2: error: ld returned 1 exit status
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.left, val) if root.val > val else searchBST(root.right, val)
We are given a binary search tree (BST) and an integer value val. Our task is to find the node in the tree with the same value as val and return the subtree rooted at that node. If there is no such node, we should return null.
To solve this problem, we use a recursive function searchBST. We first check whether the current root is null or has the value we are searching for. If either condition is true, we return the root.
Otherwise, we compare the given val with the current node's value. If val is less than the current node's value, we proceed to search the left subtree. Otherwise, we search the right subtree, and we return the result of either search.
This algorithm leverages the properties of a binary search tree, which ensures that for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node, enabling efficient search.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
return (root->val > val) ? searchBST(root->left, val) : searchBST(root->right, val);
}
We are given a binary search tree (BST) and an integer value val. Our task is to find the node in the tree with the same value as val and return the subtree rooted at that node. If there is no such node, we should return null.
To solve this problem, we use a recursive function searchBST. We first check whether the current root is null or has the value we are searching for. If either condition is true, we return the root.
Otherwise, we compare the given val with the current node's value. If val is less than the current node's value, we proceed to search the left subtree. Otherwise, we search the right subtree, and we return the result of either search.
This algorithm leverages the properties of a binary search tree, which ensures that for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node, enabling efficient search.