package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type Element struct {
	parent, left, right *Element
	key                 int
}

// NewBinarySearchTree is constructor for BinarySearchTree
func NewBinarySearchTree() *BinarySearchTree {
	bstree := BinarySearchTree{
		root: nil,
	}
	return &bstree
}

// BinarySearchTree for int
type BinarySearchTree struct {
	root *Element
}

func (t *BinarySearchTree) inorderTreeWalk(p *Element) string {
	if p == nil {
		return ""
	}

	return t.inorderTreeWalk(p.left) +
		" " + strconv.Itoa(p.key) +
		t.inorderTreeWalk(p.right)
}

func (t *BinarySearchTree) preorderTreeWalk(p *Element) string {
	if p == nil {
		return ""
	}

	return " " + strconv.Itoa(p.key) +
		t.preorderTreeWalk(p.left) +
		t.preorderTreeWalk(p.right)
}

func (t *BinarySearchTree) insert(k int) {
	newElement := Element{
		left:  nil,
		right: nil,
		key:   k,
	}

	x := t.root
	var y *Element

	for x != nil {
		y = x
		if newElement.key < x.key {
			x = x.left
		} else {
			x = x.right
		}
	}
	newElement.parent = y
	if y == nil {
		t.root = &newElement
	} else if newElement.key < y.key {
		y.left = &newElement
	} else {
		y.right = &newElement
	}
}

func (t *BinarySearchTree) search(current *Element, k int) *Element {
	for current != nil && current.key != k {
		if k < current.key {
			current = current.left
		} else {
			current = current.right
		}
	}
	return current
}

func (t *BinarySearchTree) minimum(x *Element) *Element {
	for x.left != nil {
		x = x.left
	}
	return x
}

func (t *BinarySearchTree) maximum(x *Element) *Element {
	for x.right != nil {
		x = x.right
	}
	return x
}

func (t *BinarySearchTree) successor(x *Element) *Element {
	if x.right != nil {
		return t.minimum(x.right)
	}
	y := x.parent
	for y != nil && x == y.right {
		x = y
		y = y.parent
	}
	return y
}

func (t *BinarySearchTree) transplant(target *Element, source *Element) {
	// fmt.Println(target, source, t.inorderTreeWalk(t.root))
	if target.parent == nil {
		t.root = source
	} else if target == target.parent.left {
		target.parent.left = source
	} else {
		target.parent.right = source
	}
	if source != nil {
		source.parent = target.parent
	}
}

func (t *BinarySearchTree) delete(target *Element) {
	if target.left == nil {
		t.transplant(target, target.right)
	} else if target.right == nil {
		t.transplant(target, target.left)
	} else {
		y := t.minimum(target.right)
		if y.parent != target {
			t.transplant(y, y.right)
			y.right = target.right
			y.right.parent = y
		}
		t.transplant(target, y)
		y.left = target.left
		y.left.parent = y
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	bstree := NewBinarySearchTree()

	nCommands := nextInt()
	for i := 0; i < nCommands; i++ {
		cmd := nextString()
		if cmd == "insert" {
			key := nextInt()
			bstree.insert(key)
		} else if cmd == "print" {
			fmt.Println(bstree.inorderTreeWalk(bstree.root))
			fmt.Println(bstree.preorderTreeWalk(bstree.root))
		} else if cmd == "find" {
			key := nextInt()
			r := bstree.search(bstree.root, key)
			if r != nil {
				fmt.Println("yes")
			} else {
				fmt.Println("no")
			}
		} else if cmd == "delete" {
			key := nextInt()
			target := bstree.search(bstree.root, key)
			// fmt.Println(target)
			bstree.delete(target)
		}
	}
}



Measured memory_bytes: 42956