LeetCodePractice/delete_node_in_BST.rb at main · acearth/LeetCodePractice · 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
46
47
# Q-450
def remove(tree)
  return unless tree
  return tree.left if !tree.right
  return tree.right if !tree.left
  root = tree.right
  p = tree.left
  p = p.right while p && p.right
  p.right = root.left
  root.left = tree.left
  root
end

def delete_node_recursive(tree, val)
  return unless tree
  if tree.val == val
    return remove(tree)
  elsif tree.val > val
    tree.left = delete_node(tree.left, val)
  else
    tree.right = delete_node(tree.right, val)
  end
  tree
end

def delete_node_iterate(tree, val)
  return unless tree
  return remove(tree) if tree.val == val
  pre = p = tree
  while p
    if p.val == val
      if pre.left == p
        pre.left = remove(p)
      else
        pre.right = remove(p)
      end
      break
    elsif p.val > val
      pre = p
      p = p.left
    else
      pre = p
      p = p.right
    end
  end
  tree
end