Problem:
Binary Search Tree I Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue. Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:  Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $x.key \leq y.key$.  The following figure shows an example of the binary search tree.   For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk. A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields left , right , and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. To insert a new value $v$ into a binary search tree $T$, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node $z$ for which $z.key = v$, $z.left = NIL$, and $z.right = NIL$. The procedure modifies $T$ and some of the fields of $z$ in such a way that $z$ is inserted into an appropriate position in the tree. 1 insert(T, z)
2     y = NIL // parent of x
3     x = 'the root of T'
4     while x ≠ NIL
5         y = x // set the parent
6         if z.key < x.key
7             x = x.left // move to the left child
8         else 
9             x = x.right // move to the right child
10    z.p = y
11
12    if y == NIL // T is empty
13        'the root of T' = z
14    else if z.key < y.key
15        y.left = z // z is the left child of y
16    else 
17        y.right = z // z is the right child of y Write a program which performs the following operations to a binary search tree $T$.  insert $k$: Insert a node containing $k$ as key into $T$.  print : Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.  You should use the above pseudo code to implement the insert operation. $T$ is empty at the initial state. Input In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$ or print are given. Output For each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key . Constraints  The number of operations $\leq 500,000$  The number of print operations $\leq 10$.  $-2,000,000,000 \leq key \leq 2,000,000,000$  The height of the binary tree does not exceed 100 if you employ the above pseudo code.  The keys in the binary search tree are all different.  Sample Input 1 8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print Sample Output 1 1 12 17 20 25 30 88
 30 12 1 20 17 25 88 Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
import sys


class Node(object):
    __slots__ = ['value', 'parent', 'left', 'right']
    
    def __init__(self, value: int, parent: 'Node' = None):
        self.value = value
        self.parent = parent
        self.left: Node = None
        self.right: Node = None

    def walk(self, a, walk_type):
        if walk_type == 0:
            a.append(self.value)
        if self.left:
            self.left.walk(a, walk_type)
        if walk_type == 1:
            a.append(self.value)
        if self.right:
            self.right.walk(a, walk_type)
        if walk_type == 2:
            a.append(self.value)
        return a


class BinarySearchTree(object):
    __slots__ = ['root']
    
    def __init__(self):
        self.root: Node = None

    def insert(self, x: int):
        if self.root is None:
            self.root = Node(x)
            return
        parent, current = None, self.root

        while current:
            parent = current
            if x < current.value:
                current = current.left
            else:
                current = current.right

        if x < parent.value:
            parent.left = Node(x, parent)
        else:
            parent.right = Node(x, parent)


def solve():
    tree = BinarySearchTree()
    input()
    for l in (l.split() for l in sys.stdin):
        if l[0] == "insert":
            tree.insert(int(l[1]))
        else:
            print('', *tree.root.walk([], 1))
            print('', *tree.root.walk([], 0))


if __name__ == "__main__":
    solve()

Solution (Python):
class Tree():
    def __init__(self):
        self.nodes = {}
        self.root = None

    def add_node(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)

    def insert(self, z_key):
        self.add_node(z_key)
        z = self.nodes[z_key]
        y = None  
        x = self.root
        while x is not None:
            y = x  
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def __str__(self):
        ans_in, ans_pre = [], []
        self.root.in_walk(ans_in)
        self.root.pre_walk(ans_pre)
        str_in = ' ' + ' '.join(map(str, ans_in))
        str_pre = ' ' + ' '.join(map(str, ans_pre))
        return str_in + '\n' + str_pre


class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def pre_walk(self, ans):
        ans.append(self.key)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.key)
        if self.right:
            self.right.in_walk(ans)



tree = Tree()
n = int(input())
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == 'insert':
        key = int(line[1])
        tree.insert(key)
    else:
        print(tree)

Solution (Python):
class Node:
    def __init__(self, k):
        self.parent = None
        self.childs = [None, None]
        self.key = k


class Tree:
    def __init__(self):
        self.root = None

    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.childs[0]
            else:
                x = x.childs[1]
        z.p = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.childs[0] = z
        else:
            y.childs[1] = z


def preorder(p):
    s = ""
    if p == None:
        return ""
    s += f"{p.key} "
    s += preorder(p.childs[0])
    s += preorder(p.childs[1])
    return s


def inorder(p):
    s = ""
    if p == None:
        return ""
    s += inorder(p.childs[0])
    s += f"{p.key} "
    s += inorder(p.childs[1])
    return s


n = int(input())

t = Tree()
for i in range(n):
    v = input().split()
    if v[0] == "insert":
        t.insert(Node(int(v[1])))
    else:
        print(" "+inorder(t.root).strip())
        print(" "+preorder(t.root).strip())

Solution (Python):
class Node:
    def __init__(self, value, parent):
        self.val = value
        self.left = None
        self.right = None
        self.parent = parent

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,key):
        node = Node(key, None)
        if self.root == None:
            self.root = node
        else:
            curr_node = self.root
            while curr_node:
                parent_node = curr_node
                if key <= curr_node.val:
                    curr_node = curr_node.left
                else:
                    curr_node = curr_node.right
            node.parent = parent_node
            if key <= parent_node.val:
                parent_node.left = node
            else:
                parent_node.right = node
        
    def preorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += [node.val]
        result += self.preorderTraversal(node.left)
        result += self.preorderTraversal(node.right)
        return result
        
    def inorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += self.inorderTraversal(node.left)
        result += [node.val]
        result += self.inorderTraversal(node.right)
        return result

N = int(input())
command = []
for i in range(N):
    command.append(tuple(input().split()))

T = BinarySearchTree()
for com in command:
    if com[0] == 'insert':
        T.insert(int(com[1]))
    if com[0] == 'print':
        In = T.inorderTraversal(T.root)
        Pre = T.preorderTraversal(T.root)
        print(' ' + ' '.join(list(map(str, In))))
        print(' ' + ' '.join(list(map(str, Pre))))

Solution (Python):
nodes = None


class Node:
    def __init__(self, key=None, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right


def insert(z):
    global nodes
    y = None
    x = nodes

    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right

    z.parent = y

    if y is None:
        nodes = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def get_inorder(inorder, node):
    if node.left is not None:
        get_inorder(inorder, node.left)
    inorder.append(node.key)
    if node.right is not None:
        get_inorder(inorder, node.right)
    return inorder


def get_preorder(preorder, node):
    preorder.append(node.key)
    if node.left is not None:
        get_preorder(preorder, node.left)
    if node.right is not None:
        get_preorder(preorder, node.right)
    return preorder


def p(node):
    print("", " ".join([str(i) for i in get_inorder([], node)]))
    print("", " ".join([str(i) for i in get_preorder([], node)]))


n = int(input())
for _ in range(n):
    s = input().split()
    if s[0] == "insert":
        key = int(s[1])
        insert(Node(key=key))
    else:
        p(nodes)

Solution (Python):
class Tree:
    def __init__(self):
        self.root = None
    
    def insert(self,x):
        z = Node(x)
        y = None
        x = self.root
        while x:
            y = x
            if z.data < x.data:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.data < y.data:
            y.left = z
        else:
            y.right = z

    def print(self):
        print('',' '.join(map(str,self.root.inwalk())))
        print('',' '.join(map(str,self.root.prewalk())))


class Node:
    def __init__(self,data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None

    def prewalk(self):
        ret = [self.data]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.data]
        if self.right:
            ret += self.right.inwalk()
        return ret

    
tree = Tree()
n = int(input())
for _ in range(n):
    input_line = input()
    if input_line[0] == 'i':
        tree.insert(int(input_line.split()[1]))
    else:
        tree.print()

Solution (Python):


class Node:
    def __init__(self, me, left, right):
        self.me = me
        self.left = left
        self.right = right
        self.parent = None

class NodeTree:
    def __init__(self, root=None):
        self.root = root
        
    def insert(self,z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.me < x.me:
                x = x.left
            else:
                x = x.right
        z.parent = y
        
        if y == None:
            self.root = z
        elif z.me < y.me:
            y.left = z
        else:
            y.right = z
    
    def getPreorder(self, node, ans):
        ans.append(node)
        if node.left != None:
            self.getPreorder(node.left, ans)
        if node.right != None:
            self.getPreorder(node.right, ans)
            
    def getInorder(self, node, ans):
        if node.left != None:
            self.getInorder(node.left, ans)
        ans.append(node)
        if node.right != None:
            self.getInorder(node.right, ans)

        
def printAns(ans):
    for a in ans:
        print(" " + str(a.me),end="")
    print()
    
m = int(input().rstrip())
nt = NodeTree()
for i in range(m):
    line = input().rstrip().split()
    if line[0] == "insert":
        nt.insert(Node(int(line[1]),None,None))
    else:
        ans = []
        nt.getInorder(nt.root,ans)
        printAns(ans)
        ans = []
        nt.getPreorder(nt.root,ans)
        printAns(ans)

Solution (Python):
from sys import stdin

class Node:
    def __init__(self, v, parent=None, left=None, right=None):
        self.value = v
        self.parent = parent
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def insert(self, v):
        cur = self.root
        cur_p = None
        while cur != None:
            cur_p = cur
            if v < cur.value:
                cur = cur.left
            elif v > cur.value:
                cur = cur.right

        n = Node(v, cur_p)
        if cur_p == None:
            self.root = n
        elif v < cur_p.value:
            cur_p.left = n
        else:
            cur_p.right = n

    def preorder(self):

        def rec_preorder(t=self.root):
            if t != None:
                print(" ", t.value, sep="", end="")
                rec_preorder(t.left)
                rec_preorder(t.right)

        rec_preorder()
        print()

    def inorder(self):

        def rec_inorder(t=self.root):
            if t != None:
                rec_inorder(t.left)
                print(" ", t.value, sep="", end="")
                rec_inorder(t.right)

        rec_inorder()
        print()

m = int(stdin.readline().rstrip())
t = BST()
for _ in range(m):
    q = stdin.readline().rstrip().split()
    if q[0] == "insert":
        t.insert(int(q[1]))
    elif q[0] == "print":
        t.inorder()
        t.preorder()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import defaultdict

class Node:
    def __init__(self, key):
        self.key = key
        self.par = -1
        self.left = -1
        self.right = -1

root = None
nodes = defaultdict(lambda: None)

def insert(z):
    global root
    
    y = None
    x = root
    
    while x is not None:
        y = x
        if z.key < x.key:
            
            x = nodes[x.left]
        else:
            
            x = nodes[x.right]
    if y is None:
        z.par = -1
    else:
        z.par = y.key
    
    if y is None:
        
        root = z
    elif z.key < y.key:
        
        y.left = z.key
    else:
        
        y.right = z.key

def tree_walk(node):
    preo.append(node.key)
    if node.left != -1:
        tree_walk(nodes[node.left])
    ino.append(node.key)
    if node.right != -1:
        tree_walk(nodes[node.right])
    return

N = INT()

for _ in range(N):
    instr = input()
    if instr == 'print':
        preo = []
        ino = []
        tree_walk(root)
        print('', *ino)
        print('', *preo)
    else:
        _, key = instr.split()
        key = int(key)
        node = Node(key)
        nodes[key] = node
        insert(node)

Solution (Python):
class STNode:
    def __init__(self, k, l, r):
        self.key = k
        self.left = l
        self.right = r

def STinsert(h, z):
    p = None
    while True:
        if h.key == -1:
            break
        p = h
        if z.key < h.key:
            h = h.left
        else:
            h = h.right
    if z.key < p.key:
        p.left = z
    else:
        p.right = z

def preorder(head, h, A):
    if h.key == -1:
        return
    A.append(h.key)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.key == -1:
        return
    inorder(head, h.left, B)
    B.append(h.key)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

n = int(input())
NULLnode = STNode(-1, None, None)

first = list(input().split())
head = STNode(int(first[1]), NULLnode, NULLnode)
for i in range(n-1):
    temp = list(input().split())
    if temp[0] == "insert":
        z = STNode(int(temp[1]), NULLnode, NULLnode)
        STinsert(head, z)
    else:
        A = []
        B = []
        inorder(head, head, B)
        preorder(head, head, A)

Solution (Python):

class Node:

    def __init__(self, key: int) -> None:
        self.key = key
        self.parent = None
        self.left = None
        self.right = None


def input_line() -> (str, int):
    line = input().split()
    if line[0] == 'insert':
        return 'insert', int(line[1])
    else:
        return line[0], None


def preorder(tree: Node) -> None:
    """先行順巡回。"""
    print(f' {tree.key}', end='')
    if tree.left is not None:
        preorder(tree.left)
    if tree.right is not None:
        preorder(tree.right)


def inorder(tree: Node) -> None:
    """中間順巡回。"""
    if tree.left is not None:
        inorder(tree.left)
    print(f' {tree.key}', end='')
    if tree.right is not None:
        inorder(tree.right)


def insert(new_node: Node) -> None:
    """二分探索木に挿入する。"""
    global root  
    parent = None
    x = root

    
    while x is not None:
        parent = x
        if new_node.key < x.key:
            x = x.left
        else:
            x = x.right
    new_node.parent = parent

    
    if parent is None:  
        
        root = new_node
    elif new_node.key < parent.key:
        
        parent.left = new_node
    else:
        
        parent.right = new_node


root = None  
N = int(input())
for _i in range(N):
    order, val = input_line()
    if order == 'insert':
        node = Node(val)
        insert(node)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):
class Node:
    def __init__(self,key,left,right,parent):
        self.key = key
        self.left = left
        self.right = right
        self.p = parent

    def __repr__(self):
        return str(self.key)

def insert(T, z):
    y = None
    x = T 
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    
    if y == None:
        
        T = z
        print(T)
    elif z.key<y.key:
        
        y.left = z
    else:
        
        y.right = z

def printPreorder(x):
    if x == None:
        return
    printPreorder(x.left)
    print(end=' ')
    print(x,end='')
    printPreorder(x.right)

def printMidorder(x):
    if x == None:
        return
    print(end=' ')
    print(x,end='')
    printMidorder(x.left)
    printMidorder(x.right)

def printal(x):
    printPreorder(x)
    print()
    printMidorder(x)
    print()


N = int(input())
Q = input().split()
T = Node(int(Q[1]),None,None,None)
for i in range(N-1):
    Q = input().split()
    if Q[0] == "print":
        printal(T)
        continue
    insert(T,Node(int(Q[1]),None,None,None))

Solution (Python):
def insert(z):
    global root
    y = NIL
    x = root
    
    while x != NIL:
        y = x
        if z < x:
            x = TL[x]
        else:
            x = TR[x]
    TP[z] = y

    if y == NIL:
        root = z
    elif z < y:
        TL[y] = z
    else:
        TR[y] = z


def inorder(u):
    if u == NIL:
        return
    inorder(TL[u])
    print(' ', end='')
    print(u, end='')
    inorder(TR[u])


def preorder(v):
    if v == NIL:
        return
    print(' ', end='')
    print(v, end='')
    preorder(TL[v])
    preorder(TR[v])


TR = {}
TL = {}
TP = {}
NIL = None
root = NIL
m = int(input())
data = [input().split() for _ in range(m)]

for i in data:
    if i[0][0] == 'i':
        TR[int(i[1])] = TL[int(i[1])] = NIL
        insert(int(i[1]))
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Solution (Python):
import sys


class Node:
    __slots__ = ['key', 'parent', 'left', 'right']

    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None


def insert(root, z):
    if root is None:
        return z

    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right

    z.parent = y

    if z.key < y.key:
        y.left = z
    else:
        y.right = z

    return root


def inorder(node):
    if not node:
        return
    yield from inorder(node.left)
    yield node.key
    yield from inorder(node.right)


def preorder(node):
    if not node:
        return
    yield node.key
    yield from preorder(node.left)
    yield from preorder(node.right)


def print_tree(root):
    print(''.join(' ' + str(key) for key in inorder(root)))
    print(''.join(' ' + str(key) for key in preorder(root)))


root = None

n = int(sys.stdin.readline())
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command == 'insert':
        root = insert(root, Node(int(args[0])))
    else:
        print_tree(root)

Solution (Python):




import sys
input = sys.stdin.readline
import cProfile

class node:
    def __init__(self,nodeid):
        self.parent = None
        self.c_left = None
        self.c_right = None
        self.nodeid = nodeid
    def setChild(self,n,cn=None):
        if (cn == None):
            cn = self
        if ( cn.nodeid < n):
            if (cn.c_right == None):
                cn.c_right = node(n) 
                cn.c_right.parent =  cn 
                return cn.c_right
            else:
                return self.setChild(n,cn.c_right)
        else:
            if (cn.c_left == None):
                cn.c_left = node(n) 
                cn.c_left.parent =  cn
                return cn.c_left 
            else:
                return self.setChild(n,cn.c_left)

    def getPreorder(self,r1=[]):
        r1.append(self.nodeid)
        if (self.c_left != None):
            r1 = self.c_left.getPreorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPreorder(r1)
        return r1       
    def getInorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getInorder(r1)
        r1.append(self.nodeid)
        if (self.c_right != None):
            r1 = self.c_right.getInorder(r1)
        return r1       
    def getPostorder(self,r1=[]):
        if (self.c_left != None):
            r1 = self.c_left.getPostorder(r1)
        if (self.c_right != None):
            r1 = self.c_right.getPostorder(r1)
        r1.append(self.nodeid)
        return r1       
    def find(self,n):
        if self.nodeid == n:
            return True
        if self.nodeid > n:
            if (self.c_left == None ):
                return False
            return self.c_left.find(n)
        else:
            if  (self.c_right == None):
                return False
            return self.c_right.find(n)

    def findObject(self,n):
        if self.nodeid == n:
            return self
        if self.nodeid > n:
            if (self.c_left == None ):
                return None
            return self.c_left.findObject(n)
        else:
            if  (self.c_right == None):
                return None
            return self.c_right.findObject(n)

    def deleteNum(self,n):
        i = self.findObject(int(n))
        if i == None:
            return False
        self.deleteObject(i)
        return True

    def deleteObject(self,obj):
        p = obj.parent
        x = obj
        if x.c_left == None and x.c_right == None:
            if p.c_right.nodeid == x.nodeid:
                p.c_right = None
            else:
                p.c_left = None
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left == None and x.c_right != None:
            if p.c_right != None and p.c_right.nodeid == obj.nodeid:
                p.c_right = x.c_right
                x.c_right.parent = p
            else:
                p.c_left = x.c_right
                x.c_right.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left != None and x.c_right == None:
            if p.c_right.nodeid == x.nodeid:
                p.c_right = x.c_left
                x.c_left.parent = p
            else:
                p.c_left = x.c_left
                x.c_left.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        y = self.findMinObject(x.c_right)
        x.nodeid = y.nodeid
        p = y.parent
        x = y
        if x.c_left == None and x.c_right == None:
            if p.c_right != None and p.c_right.nodeid == x.nodeid:
                p.c_right = None
            else:
                p.c_left = None
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

        if x.c_left == None and x.c_right != None:
            if p.c_right.nodeid == obj.nodeid:
                p.c_right = x.c_right
                x.c_right.parent = p
            else:
                p.c_left = x.c_right
                x.c_right.parent = p
            x.nodeid = -1
            x.parent = None
            x.c_right = None
            x.c_left = None
            return

    def findMinObject(self,obj):
        i = obj
        while i != None and i.c_left != None:
            i = i.c_left
        return i

    
    def getRoot(self):
        if (self.parent == None):
            return self
        return self.parent.getRoot()

def printNodeList(nodelist,caption):
    for i in nodelist:
        a = b = c = None
        if (i != None ):
            a = i.nodeid
        if (i.c_left != None):
            b = i.c_left.nodeid
        if (i.c_right != None):
            c = i.c_right.nodeid 
        if ( a != None and (b != None or c != None)):
            print (caption,a,b,c)
            
def main():
    n = int(input())
    nodelist = []
    root = None
    for i in range(n):
        l = list(map(str,input().split()))
        if (l[0] == "print" and root != None):
            print("",*root.getInorder([]))
            print("",*root.getPreorder([]))
        elif (l[0] == "insert"):
            d = int(l[1])
            if ( root == None):
                root = node(d)
                nodelist.append(root)
            else:
                
                nodelist.append(root.setChild(d))
        elif (l[0] == "find"):
            d = int(l[1])
            r = root.find(d)
            if (r == True):
                print ("yes")
            else:
                print ("no")
        elif (l[0] == "delete"):
            
            root.deleteNum(l[1])
            

        
if __name__ == '__main__':
    main()

Solution (Python):
import sys
class Node:
    parent = -1
    left = -1
    right = -1

    def __init__(self, key):
        self.key = key

    def __repr__(self):
        return "key:{},parent:{},left:{},right:{}".format(self.key, self.parent, self.left, self.right)

root_node_no = -1

def insert(nodes :dict, in_node :Node):
    global root_node_no

    cur_node_no = root_node_no
    parent_node_no = -1
    while cur_node_no != -1:
        parent_node_no = cur_node_no
        if in_node.key < cur_node_no:
            cur_node_no = nodes[cur_node_no].left
        else:
            cur_node_no = nodes[cur_node_no].right

    in_node.parent = parent_node_no

    if root_node_no == -1:
        root_node_no = in_node.key
    elif in_node.key < parent_node_no:
        nodes[parent_node_no].left = in_node.key
    else:
        nodes[parent_node_no].right = in_node.key

    nodes[in_node.key] = in_node

def inorder_tree_walk(nodes, node_no ,inorder):
    if node_no == -1:
        return
    inorder_tree_walk(nodes, nodes[node_no].left, inorder)
    inorder.append(node_no)
    inorder_tree_walk(nodes, nodes[node_no].right, inorder)

def preorder_tree_walk(nodes, node_no, preorder):
    if node_no == -1:
        return
    preorder.append(node_no)
    preorder_tree_walk(nodes, nodes[node_no].left, preorder)
    preorder_tree_walk(nodes, nodes[node_no].right, preorder)
    pass

def main():
    num_com = int(input())
    commands = sys.stdin.readlines()
    nodes = {}
    for i in range(num_com):
        if commands[i][0] == 'i':
            insert(nodes, Node(int(commands[i][7:])))
        elif commands[i][0] == 'p':
            
            inorder = []
            inorder_tree_walk(nodes, root_node_no, inorder)
            print(" " + " ".join(map(str, inorder)))
            
            preorder = []
            preorder_tree_walk(nodes, root_node_no, preorder)
            print(" " + " ".join(map(str, preorder)))


main()

Solution (Python):
class Node:
    def __init__(self,key):
        self.key=key
        self.left=None
        self.right=None


def insert(root,node):
    if(root.key <= node.key):
        if(root.right is None):
            root.right=node
        else:
            insert(root.right,node)
    
    else:
        if(root.left is None):
            root.left=node
        else:
            insert(root.left,node)


def Preorder(root,order):
    order.append(root.key)
    if(root.left is not None):
        Preorder(root.left,order)
    
    if(root.right is not None):
        Preorder(root.right,order)




def Inorder(root,order):
    if(root.left is not None):
        Inorder(root.left,order)
    
    order.append(root.key)

    if(root.right is not None):
        Inorder(root.right,order)




n=int(input())

root=None

for loop in range(n):
    ope=input().split()

    if(ope[0]=="insert"):
        tmp_node=Node(int(ope[1]))
        try:
            insert(root,tmp_node)
        except:
            root=tmp_node
    
    else:
        in_order=[]
        p_order=[]
        
        Inorder(root,in_order)
        Preorder(root,p_order)

        for x in in_order:
            print(f" {x}",end="")
        print()
        for x in p_order:
            print(f" {x}",end="")
        print()