Programming Project: Implement following binary$-$search tree functions:

$-$ search$($key$)$

$-$ insert$($key$)$

$-$ print$\_$in$\_$order$()$: prints the keys in the binary tree in ascending order.

Use the base code below:

import queue

class LinkedBinaryTree:

class $\_$Node:

$\_\_$slots$\_\_=\text{'}\_$el$\text{'},\text{'}\_$l$\text{'},\text{'}\_$r$\text{'}$

def $\_\_$init$\_\_($self$,$ element, left$=$None, right$=$None$)$:

self.$\_$el $=$ element

self.$\_$l $=$ left

self.$\_$r $=$ right

def $\_\_$init$\_\_($self$)$:

self.$\_$root $=$ None

self.$\_$size $=0$

def $\_\_$len$\_\_($self$)$:

return self.$\_$size

def height$($self$)$:

return self.$\_$height$($self$.\_$root$)$

def $\_$height$($self$,$ p$)$:

if not p:

return $0$

return $1+$ max$($self$.\_$height$($p$.\_$l$),$ self.$\_$height$($p$.\_$r$))$

def $\_$in$\_$order$($self$,$ p$)$:

if p:

yield from self.$\_$in$\_$order$($p$.\_$l$)$

yield p$.\_$el

yield from self.$\_$in$\_$order$($p$.\_$r$)$

def $\_$pre$\_$order$($self$,$ p$)$:

if p:

yield p$.\_$el

yield from self.$\_$pre$\_$order$($p$.\_$l$)$

yield from self.$\_$pre$\_$order$($p$.\_$r$)$

def $\_$post$\_$order$($self$,$ p$)$:

if p:

yield from self.$\_$post$\_$order$($p$.\_$l$)$

yield from self.$\_$post$\_$order$($p$.\_$r$)$

yield p$.\_$el

def breadth$\_$first$($self$)$:

q $=$ queue.Queue$()$

q$.$put$($self$.\_$root$)$

while not q$.$empty$()$:

p $=$ q$.$get$()$

if p:

print$($p$.\_$el$)$

if p$.\_$l:

q$.$put$($p$.\_$l$)$

if p$.\_$r:

q$.$put$($p$.\_$r$)$

def bst$\_$insert$($self$,$ key$)$:

if self.$\_$root is None:

self.$\_$root $=$ self.$\_$Node$($key$)$

else:

self.$\_$bst$\_$insert$($self$.\_$root, key$)$

self.$\_$size $+=1$

def $\_$bst$\_$insert$($self$,$ node, key$)$:

# Your code here

pass

def bst$\_$search$($self$,$ key$)$:

return self.$\_$bst$\_$search$($self$.\_$root, key$)$

def $\_$bst$\_$search$($self$,$ node, key$)$:

# Your code here

pass

def print$\_$in$\_$order$($self$)$:

# Your code here

pass

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

tree $=$ LinkedBinaryTree$()$

for value in $[7,3,2,5,6,9,1,4,8,10]$:

tree.bst$\_$insert$($value$)$

print$("$Search for $4$:$",$ tree.bst$\_$search$(4))$ # true

print$("$Search for $2$:$",$ tree.bst$\_$search$(2))$ # false

print$("$In$-$order traversal:"$)$

tree.print$\_$in$\_$order$()$