LeetCode Binary Search Tree

Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
return helper(root, Int.min, Int.max)
}

private func helper(_ node: TreeNode?, _ lower: Int, _ upper: Int) -> Bool {
guard let n = node else { return true }
if n.val <= lower || n.val >= upper { return false }

return helper(n.left, lower, n.val) && helper(n.right, n.val, upper)
}
}

Binary Search Tree Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BSTIterator {

private var queue = [Int]()
private func helper(_ root: TreeNode?) {
guard let root = root else { return }
helper(root.left)
queue.append(root.val)
helper(root.right)
}

init(_ root: TreeNode?) {
helper(root)
}

func next() -> Int {
return queue.removeFirst()
}

func hasNext() -> Bool {
return !queue.isEmpty
}
}

Search in a Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let root = root else { return nil }
if root.val == val { return root }
if val < root.val {
return searchBST(root.left, val)
} else {
return searchBST(root.right, val)
}
}
}

Insert into a Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
func insert(_ root: TreeNode? = root, _ val: Int = val) {
guard let root = root else { return }
if val < root.val {
if let l = root.left {
insert(l, val)
} else {
root.left = TreeNode(val)
}
} else {
if let r = root.right {
insert(r, val)
} else {
root.right = TreeNode(val)
}
}
}
insert()
return root ?? TreeNode(val)
}
}

Delete Node in a Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
guard let root = root else { return nil }
if root.val == key {
if root.left != nil && root.right != nil {
var p = root.right
while p?.left != nil { p = p?.left }
p?.left = root.left
return root.right
} else {
return root.left != nil ? root.left : root.right
}
} else if key < root.val {
root.left = deleteNode(root.left, key)
} else {
root.right = deleteNode(root.right, key)
}
return root
}
}

Kth Largest Element in a Stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class KthLargest {

var arr = [Int]()
var k = 0
init(_ k: Int, _ nums: [Int]) {
self.k = k
for i in nums { add(i) }
}

func add(_ val: Int) -> Int {
if arr.count < k || val > arr.first! {
var i = 0
while i < arr.count, val > arr[i] {
i += 1
}
arr.insert(val, at: i)
if arr.count > k {
arr.removeFirst()
}
}
return arr.first!
}

}

Lowest Common Ancestor of a Binary Search Tree

1
2
3
4
5
6
7
class Solution {
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
guard let root = root, let pv = p?.val, let qv = q?.val else { return nil }
if root.val >= min(pv, qv) && root.val <= max(pv, qv) { return root }
return root.val > max(pv, qv) ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q)
}
}

Contains Duplicate III

1

Balanced Binary Tree

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func isBalanced(_ root: TreeNode?) -> Bool {
return helper(root).1
}

func helper(_ root: TreeNode?) -> (Int, Bool) {
guard let r = root else { return (0, true) }
let rl = helper(r.left), rr = helper(r.right)
return (1 + max(rl.0, rr.0), rl.1 && rr.1 && abs(rl.0 - rr.0) <= 1)
}
}

Convert Sorted Array to Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
if nums.isEmpty { return nil }
let n = nums.count, h = n/2, h1 = h+1

let r = TreeNode(nums[n/2])
r.left = sortedArrayToBST(Array(nums[0..<h]))
r.right = sortedArrayToBST(Array(nums[h1...]))
return r
}
}

Translated by gpt-3.5-turbo