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):
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

root = None
def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z[2] < x[2]:
            x = x[0]
        else:
            x = x[1]
    z[3] = y

    if y is None:
        root = z
    elif z[2] < y[2]:
        y[0] = z
    else:
        y[1] = z

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0] is not None:
            dfs(nd[0])
        s1.append(v)
        if nd[1] is not None:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    else:
        insert([None, None, int(V[0]), None])
write("\n".join(ans))
write("\n")

Solution (Python):
import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            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, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        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.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

Solution (Python):
from sys import stdin

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

class BinarySearchTree(object):
    def __init__(self):
        self.tree = {}
        self.root = None

    def insert(self, z):
        if not self.tree:
            self.tree[z] = Node(parent=-1)
            self.root = z
        else:
            x = self.root
            while x != None:
                y = x
                if z < x:
                    x = self.tree[x].left
                else:
                    x = self.tree[x].right

            self.tree[z] = Node(parent=y)
            if z < y:
                self.tree[y].left = z
            else:
                self.tree[y].right = z

    def print_nodes(self):
        A = [] 
        B = [] 
        def walk_tree(u):
            if u == None:
                return
            r = self.tree[u].right
            l = self.tree[u].left
            A.append(u)
            walk_tree(l)
            B.append(u)
            walk_tree(r)

        walk_tree(self.root)
        print(" ", end="")
        print(*B, sep=" ")
        print(" ", end="")
        print(*A, sep=" ")

def read_and_print_BSTree(bst, n):
    for _ in range(n):
        cmd = stdin.readline().strip().split()
        if cmd[0] == 'insert':
            bst.insert(int(cmd[1]))
        elif cmd[0] == 'print':
            bst.print_nodes()

n = int(input())
bst = BinarySearchTree()
read_and_print_BSTree(bst, n)

Solution (Python):
import sys
class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    y = None  
    x = root
    while x:
        y = x
        x = x.left if key < x.key else x.right
    if y is None:  
        root = Node(key)
    elif key < y.key:
        y.left = Node(key)
    else:
        y.right = Node(key)

def in_order(node):
    if node is None:
        return ''
    return in_order(node.left) + f' {node.key}' + in_order(node.right)
def pre_order(node):
    if node is None:
        return ''
    return f' {node.key}' + pre_order(node.left) + pre_order(node.right)
input()
for e in sys.stdin:
    if e[0] == 'i':
        insert(int(e[7:]))
    else:
        print(in_order(root))
        print(pre_order(root))

Solution (Python):



from sys import stdin


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.left
            else:
                x = x.right

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

    def print_inorder(self):
        def rec(node):
            if not node:
                return
            else:
                rec(node.left)
                print("", node.key, end="")
                rec(node.right)

        rec(self.root)
        print()

    def print_preorder(self):

        def rec(node):
            if not node:
                return
            else:
                print("", node.key, end="")
                rec(node.left)
                rec(node.right)

        rec(self.root)
        print()


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

    def __repr__(self):
        return "Node({}, {}, {})".format(
            self.val, self.left, self.right)


def main():
    _ = int(stdin.readline())
    T = Tree()

    for line in stdin:
        cmd, *args = line.split()
        if cmd == "insert":
            T.insert(Node(int(args[0])))
        elif cmd == "print":
            T.print_inorder()
            T.print_preorder()


main()

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
        
    def insert(self, z):
        if z.key < self.key:
            if self.left:
                self.left.insert(z)
            else:
                self.left = z
                z.parent = self
        else:
            if self.right:
                self.right.insert(z)
            else:
                self.right = z
                z.parent = self

    def preo(self):
        tmp = ""
        tmp += " " + str(self.key)
        if self.left:
            tmp += self.left.preo()
        if self.right:
            tmp += self.right.preo()
        return tmp
    
    def ino(self):
        tmp = ""
        if self.left:
            tmp += self.left.ino()
        tmp += " " + str(self.key)
        if self.right:
            tmp += self.right.ino()
        return tmp
    
    
m = int(input())
T = {}
for i in range(m):
    com = input().split()
    if com[0] == "insert":
        node = Node(int(com[1]))
        if len(T)==0:
            T[node.key] = node
            T["root"] = node
        else:
            T["root"].insert(node)
    else:
        print(T["root"].ino())
        print(T["root"].preo())

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

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

    def insert(self, node):
        y = None                 
        x = self.root
        while x is not None:
            y = x                
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
        node.parent = y

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

    def parse_inorder(self, node):
        if node is None:
            return 
        self.parse_inorder(node.left)
        self.list.append(node.key)
        self.parse_inorder(node.right)

    def parse_preorder(self, node):
        if node is None:
            return
        self.list.append(node.key)
        self.parse_preorder(node.left)
        self.parse_preorder(node.right)

N = int(input())
T = Tree()
for i in range(N):
    order, *key = input().split()
    if order == "print":
        T.list = []
        T.parse_inorder(T.root)
        print(" " + " ".join(map(str, T.list)))
        T.list = []
        T.parse_preorder(T.root)
        print(" " + " ".join(map(str, T.list)))
    else:
        node = Node(int(key[0]))
        T.insert(node)

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


root = None

def insert(k):
    global root
    y = None
    x = root
    z = Node(k)

    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:
        root = z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z


def inorder(u):
    if u is None:
        return
    inorder(u.left)
    print(' %d' % u.key, end='')
    inorder(u.right)


def preorder(u):
    if u is None:
        return
    print(' %d' % u.key, end='')
    preorder(u.left)
    preorder(u.right)


n = int(input())
for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        insert(int(cmd[1]))
    elif cmd[0] == 'print':
        inorder(root)
        print()
        preorder(root)
        print()

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

class BST:
	def __init__(self):
		self.root = None
	
	def insert(self, key):
		new = Node(key)
		parent = None
		current = self.root
		while current != None:
			parent = current
			if key < current.key:
				current = current.left
			else:
				current = current.right
		if parent == None:
			self.root = new
		elif key < parent.key:
			parent.left = new
		else:
			parent.right = new		
	
	def find(self, key):
		return
		
	def delete(self, key):
		return
	
	def print(self):
		self.print_in_order(self.root)
		print()
		self.print_pre_order(self.root)
		print()
		
	def print_in_order(self, node):
		if node != None:
			self.print_in_order(node.left)
			print(' ' + str(node.key), end='')
			self.print_in_order(node.right)
		
	def print_pre_order(self, node):
		if node != None:
			print(' ' + str(node.key), end='')
			self.print_pre_order(node.left)
			self.print_pre_order(node.right)		

n = int(input())
bst = BST()
for i in range(n):
	cmd = list(map(str, input().split()))
	if cmd[0] == 'print':
		bst.print()
	else:
		key = int(cmd[1])
		if cmd[0] == 'insert':
			bst.insert(key)
		elif cmd[0] == 'find':
			bst.find(key)
		else:
			bst.delete(key)

Solution (Python):

class Tree:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def printorder(self):
        self._preorder_walk(self.root)
        print()
        self._inorder_walk(self.root)
        print()

    def _inorder_walk(self, nd):
        print(' {0}'.format(nd.key), end='')
        if nd.left: self._inorder_walk(nd.left)
        if nd.right: self._inorder_walk(nd.right)

    def _preorder_walk(self, nd):
        if nd.left: self._preorder_walk(nd.left)
        print(' {0}'.format(nd.key), end='')
        if nd.right: self._preorder_walk(nd.right)

class Node:
    def num_child(self):
        d = 1 if self.left else 0
        d += 1 if self.right else 0
        return d
    def __init__(self, key):
        self.key = key
        self.right,self.left = None,None
        self.parent = None
    def __str__(self):
        return 'node key: ' + str(self.key)

def insert(T, z):
    y = None
    x = T.root
    while not x == None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if z.parent == None:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    T.size += 1

m = int(input())
T = Tree()
for _ in range(m):
    ss = input().split()
    op = ss[0]
    if op == 'insert':
        v = int(ss[1])
        insert(T, Node(v))
    if op == 'print':
        T.printorder()