-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinimumDistanceBetweenBstNodes.ts
110 lines (98 loc) · 2.82 KB
/
MinimumDistanceBetweenBstNodes.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Source : https://leetcode.com/problems/minimum-distance-between-bst-nodes/
// Author : squxq
// Date : 2023-11-06
/*****************************************************************************************************
*
* 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:
*
* The number of nodes in the tree is in the range [2, 100].
* 0 <= Node.val <= 10^5
*
* Note: This question is the same as 530:
* https://leetcode.com/problems/minimum-absolute-difference-in-bst/
******************************************************************************************************/
/**
* Binary Search Tree (BST) is one of:
* - null
* - NodeTree
* interp. null means no BST, or empty BST; NodeTree is the root node of the BST
*/
export type BST = NodeTree | null;
/**
* NodeTree is new NodeTree(number, BST, BST)
* interp. new NodeTree(val, left, right) is a BST's node with:
* - val, is the node's key
* - left, is the node's left subtree
* - right, is the node's right subtree
* INVARIANT (for a given node):
* - val is greater (>) than all the keys (val) in its left child (left)
* - val is smaller (<) than all the keys (val) in its right child (right)
* - the same key (val) never appears twice in the tree
*/
export class NodeTree {
val: number;
left: BST;
right: BST;
constructor(val: number = 0, left: BST = null, right: BST = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Template:
* function fn-for-bst(bst: BST) {
if (bst === null) {return (...)}
else {
return (...
(bst.val)
(fn-for-bst (bst.left))
(fn-for-bst (bst.right)))
}
}
*/
/**
* BST -> number
* given the root of a BST, root, return the minimum distance between the values of any two different nodes in the tree
* CONSTRAINTS: the number of nodes in the tree is in the range [2,100]
* 0 <= Node.val <= 10^5
* Stub:
* function minDiffInBST(root: BST): number {return 0}
* Tests:
* root = [4,2,6,1,3] -> output = 1
* root = [1,0,48,null,null,12,49] -> output = 1
* Template: <used template from BST>
*/
export function minDiffInBST(root: BST): number {
let prev: number = NaN;
let min: number = Infinity;
function inOrderTraversal(node: BST): void {
if (node !== null) {
inOrderTraversal(node.left);
const diff: number = Math.abs(node.val - prev);
if (diff === 0) {
min = 0;
return;
} else if (diff < min) {
min = diff;
}
prev = node.val;
inOrderTraversal(node.right);
}
}
inOrderTraversal(root);
return min;
}