package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var root *elem
	for i := 0; i < n; i++ {
		sc.Scan()
		line := sc.Text()
		if line == "print" {
			printIn(root)
			fmt.Println(strings.Join(in, ""))
			printPre(root)
			fmt.Println(strings.Join(pre, ""))
			in = []string{}
			pre = []string{}
			// printDebug(root)
		} else if line == "find" {
			sc.Scan()
			num, _ := strconv.Atoi(sc.Text())
			if find(root, num) == nil {
				fmt.Println("no")
			} else {
				fmt.Println("yes")
			}
		} else if line == "delete" {
			sc.Scan()
			num, _ := strconv.Atoi(sc.Text())
			delete(root, num)
			// printDebug(root)
		} else {
			sc.Scan()
			num, _ := strconv.Atoi(sc.Text())
			root = insert(root, num)
		}
	}
}

func printDebug(elem *elem) {
	pk := -1
	if elem.parent != nil {
		pk = elem.parent.key
	}

	lk := -1
	if elem.left != nil {
		lk = elem.left.key
	}

	rk := -1
	if elem.right != nil {
		rk = elem.right.key
	}

	fmt.Printf("====DEBUG==== KEY:%v, PARENT:%v, LEFT:%v. RIGHT:%v\n", elem.key, pk, lk, rk)
	if elem.left != nil {
		printDebug(elem.left)
	}
	if elem.right != nil {
		printDebug(elem.right)
	}

}

var pre []string

func printPre(elem *elem) {
	if elem == nil {
		return
	}
	pre = append(pre, " "+strconv.Itoa(elem.key))
	printPre(elem.left)
	printPre(elem.right)
}

var in []string

func printIn(elem *elem) {
	if elem == nil {
		return
	}
	printIn(elem.left)
	in = append(in, " "+strconv.Itoa(elem.key))
	printIn(elem.right)
}

type elem struct {
	parent *elem
	left   *elem
	right  *elem
	key    int
}

func insert(root *elem, zkey int) *elem {
	// new Value
	z := &elem{nil, nil, nil, zkey}
	if root == nil {
		return z
	}

	// search parent
	parentOfZ := root
	for {
		if parentOfZ.key > z.key {
			if parentOfZ.left == nil {
				parentOfZ.left = z
				break
			}
			parentOfZ = parentOfZ.left
		} else {
			if parentOfZ.right == nil {
				parentOfZ.right = z
				break
			}
			parentOfZ = parentOfZ.right
		}
	}

	z.parent = parentOfZ
	return root
}

func delete(root *elem, target int) {
	// fmt.Printf("TARGET:%v\n", target)
	te := find(root, target)
	// if te doesn't have any child
	if hasChild(te) == false {
		deleteSelf(te)
		// fmt.Println(1)
		return
	}

	// if te have only one child
	if te.left == nil {
		// te has right
		if isLeftChild(te) {
			te.parent.left = te.right
			te.right.parent = te.parent
		} else {
			te.parent.right = te.right
			te.right.parent = te.parent
		}
		// fmt.Println(2)

		return
	} else if te.right == nil {
		// te has left
		if isLeftChild(te) {
			te.parent.left = te.left
			te.left.parent = te.parent
		} else {
			te.parent.right = te.left
			te.left.parent = te.parent
		}
		// fmt.Println(3)
		return
	}

	// te has two children
	// fmt.Println("DELETE")
	next := getNextPoint(te)
	te.key = next.key
	deleteSelf(next)
}

func getNextPoint(elem *elem) *elem {
	// elem doesn't have right children
	if elem.right == nil {
		// elem is left child
		// 	next is parent
		if isLeftChild(elem) {
			return elem.parent
		}
		// elem is right child
		// 	next is parent of parent? (or no next)
		// ?????
		return elem.parent.parent
	}

	// elem has right children
	// next is minimum at right children
	return getMinimum(elem.right)

}

func getMinimum(elem *elem) *elem {
	if elem.left != nil {
		return getMinimum(elem.left)
	}
	return elem
}

func hasChild(e *elem) bool {
	return e.left != nil || e.right != nil
}

func isLeftChild(e *elem) bool {
	if e.parent == nil {
		return false
	}
	if e.parent.left == nil {
		return false
	}

	return e.parent.left.key == e.key
}

func isRightChild(e *elem) bool {
	if e.parent == nil {
		return false
	}
	if e.parent.right == nil {
		return false
	}

	return e.parent.right.key == e.key
}

func deleteSelf(e *elem) {
	if e.left != nil {
		e.left.parent = nil
	}

	if e.right != nil {
		e.right.parent = nil
	}

	if isLeftChild(e) {
		e.parent.left = nil
	} else if isRightChild(e) {
		e.parent.right = nil
	}
}

func find(root *elem, zkey int) *elem {
	// search parent
	s := root
	for {

		if s.key == zkey {
			return s
		}

		if s.key > zkey {
			if s.left == nil {
				break
			}
			s = s.left
		} else {
			if s.right == nil {
				break
			}
			s = s.right
		}
	}
	return nil
}



Measured memory_bytes: 80852