leetcode-ruby/lib/medium/450_delete_node_in_a_bst.rb at master · fartem/leetcode-ruby · GitHub

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
# frozen_string_literal: true

# https://leetcode.com/problems/delete-node-in-a-bst/
# @param {TreeNode} root
# @param {Integer} key
# @return {TreeNode}
def delete_node450(root, key)
  return unless root

  if key > root.val
    root.right = delete_node450(root.right, key)
  elsif key < root.val
    root.left = delete_node450(root.left, key)
  elsif !root.left && !root.right
    root = nil
  elsif root.right
    root.val = successor(root)
    root.right = delete_node450(root.right, root.val)
  else
    root.val = predecessor(root)
    root.left = delete_node450(root.left, root.val)
  end

  root
end

private

# @param {TreeNode} node
# @return {Integer}
def successor(node)
  node = node.right
  node = node.left while node.left

  node.val
end

# @param {TreeNode} node
# @return {Integer}
def predecessor(node)
  node = node.left
  node = node.right while node.right

  node.val
end