package main

type Node struct {
	Value  int
	Parent *Node
	Left   *Node
	Right  *Node
}

func NewNode(v int) *Node {
	return &Node{Value: v}
}

func (n *Node) Compare(m *Node) int {
	if n.Value < m.Value {
		return -1
	} else if n.Value > m.Value {
		return 1
	}
	return 0
}

type BST struct {
	Root *Node
	Size int
}

func NewBST(n *Node) *BST {
	if n == nil {
		return &BST{}
	}
	return &BST{Root: n, Size: 1}
}

func (t *BST) Search(v int) *Node {
	n := NewNode(v)
	h := t.Root
	for h != nil {
		switch n.Compare(h) {
		case -1:
			h = h.Left
		case 1:
			h = h.Right
		default:
			return h
		}
	}
	return nil
}

func (t *BST) Max() *Node {
	if t.Root == nil {
		return nil
	}
	max := t.Root
	for max.Right != nil {
		max = max.Right
	}
	return max
}

func (t *BST) Min() *Node {
	if t.Root == nil {
		return nil
	}
	min := t.Root
	for min.Left != nil {
		min = min.Left
	}
	return min
}

func (t *BST) Insert(v int) {
	n := NewNode(v)
	if t.Root == nil {
		t.Root = n
		t.Size++
		return
	}
	h := t.Root
	for {
		switch n.Compare(h) {
		case -1:
			if h.Left == nil {
				h.Left = n
				t.Size++
				return
			} else {
				h = h.Left
			}
		case 1:
			if h.Right == nil {
				h.Right = n
				t.Size++
				return
			} else {
				h = h.Right
			}
		default:
			return
		}
	}
}

func (t *BST) Traverse(n *Node, f func(*Node)) {
	if n == nil {
		return
	}
	t.Traverse(n.Right, f)
	f(n)
	t.Traverse(n.Left, f)
}

func (t *BST) Delete(v int) {
	var parent *Node
	h := t.Root
	n := NewNode(v)
	for h != nil {
		switch n.Compare(h) {
		case -1:
			parent = h
			h = h.Left
		case 1:
			parent = h
			h = h.Right
		default:
			if h.Left != nil {
				right := h.Right
				h.Value = h.Left.Value
				h.Right = h.Left.Right
				h.Left = h.Left.Left
				if right != nil {
					st := &BST{Root: h}
					t.Traverse(right, func(n *Node) {
						st.Insert(n.Value)
					})
				}
				t.Size--
				return
			}

			if h.Right != nil {
				h.Value = h.Right.Value
				h.Left = h.Right.Left
				h.Right = h.Right.Right
				t.Size--
				return
			}

			if parent == nil {
				t.Root = nil
				t.Size--
				return
			}
			if parent.Left.Value == n.Value {
				parent.Left = nil
			} else {
				parent.Right = nil
			}
			t.Size--
			return
		}
	}
}