Chapter $8-$ Programming Project: Implement the binary tree ADT using a linked structure as we developed in class, add the following methods:

$-$def countK$($self$,$ num$)$: function that takes in num and counts number of times num appears in the binary tree

$-$def equal$($self$,$ other: BinaryTree$)$: function thats takes in another binary tree $($other$)$ as parameter and returns true if both binary trees are equal, otherwise function returns False.

Use the base code provided:

class BinaryTree:

class $\_$Node:

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

self.$\_$left $=$ left

self.$\_$right $=$ right

self.$\_$element $=$ e

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

self.$\_$root $=$ None

self.$\_$size $=0$

def is$\_$empty$($self$)$:

return self.$\_$root is None

def add$\_$root$($self$,$ e$)$:

if self.$\_$root:

return None

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

return self.$\_$root

def add$\_$left$($self$,$ e$,$ p$)$:

p$.\_$left $=$ self.$\_$Node$($e$)$

return p$.\_$left

def add$\_$right$($self$,$ e$,$ p$)$:

p$.\_$right $=$ self.$\_$Node$($e$)$

return p$.\_$right

def height$($self$)$:

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

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

if not v:

return $-1$

x $=$ self.$\_$height$($v$.\_$left$)$

y $=$ self.$\_$height$($v$.\_$right$)$

return $1+$ max$($x$,$ y$)$

def countK$($self$,$ k$)$:

# Write code here

$$ # Pseudocode for countK function

$"""$

$1.$ Initialize a variable 'count' to $0.$

$2.$ Create a helper function $\text{'}\_$countK' that takes a node and a number as arguments.

$2\mathrm{.}1.$ If the node is None, return $0.$

$2\mathrm{.}2.$ If the node's element is equal to the given number, increment 'count' by $1.$

$2\mathrm{.}3.$ Recursively call $\text{'}\_$countK' for the left and right children of the node.

$2\mathrm{.}4.$ Return the count.

$3.$ Call the helper function $\text{'}\_$countK' starting from the root of the tree.

$4.$ Return the count.

$"""$

def $\_$countK$($self$,$ p$,$ k$)$:

# Write code here

def equal$($self$,$ other$)$:

# Write code here

# Pseudocode for equal function

$"""$

$1.$ Create a helper function $\text{'}\_$equal' that takes two nodes as arguments.

$1\mathrm{.}1.$ If both nodes are None, return True.

$1\mathrm{.}2.$ If one of the nodes is None and the other is not, return False.

$1\mathrm{.}3.$ If the elements of the two nodes are not equal, return False.

$1\mathrm{.}4.$ Recursively call $\text{'}\_$equal' for the left children of both nodes.

$1\mathrm{.}5.$ Recursively call $\text{'}\_$equal' for the right children of both nodes.

$1\mathrm{.}6.$ If both recursive calls return True, return True. Otherwise, return False.

$2.$ Call the helper function $\text{'}\_$equal' with the root nodes of both trees.

$3.$ Return the result.

$"""$

def $\_$equal$($self$,$ p$1,$ p$2)$:

# Write code here

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

bt$1=$ BinaryTree$()$

root$1=$ bt$1.$add$\_$root$(10)$

# Create a tree with height $5$ and multiple $7\text{'}$s in it

left$\_$child$1=$ bt$1.$add$\_$left$(7,$ root$1)$

right$\_$child$1=$ bt$1.$add$\_$right$(7,$ root$1)$

l$1=$ bt$1.$add$\_$left$(5,$ left$\_$child$1)$

r$1=$ bt$1.$add$\_$right$(7,$ left$\_$child$1)$

l$2=$ bt$1.$add$\_$left$(3,$ l$1)$

r$2=$ bt$1.$add$\_$right$(6,$ l$1)$

l$3=$ bt$1.$add$\_$left$(7,$ l$2)$

r$3=$ bt$1.$add$\_$right$(4,$ l$2)$

bt$1.$add$\_$left$(1,$ l$3)$

bt$1.$add$\_$right$(7,$ l$3)$

bt$2=$ BinaryTree$()$

root$2=$ bt$2.$add$\_$root$(10)$

# Create another identical tree

left$\_$child$2=$ bt$2.$add$\_$left$(7,$ root$2)$

right$\_$child$2=$ bt$2.$add$\_$right$(7,$ root$2)$

l$1=$ bt$2.$add$\_$left$(5,$ left$\_$child$2)$

r$1=$ bt$2.$add$\_$right$(7,$ left$\_$child$2)$

l$2=$ bt$2.$add$\_$left$(3,$ l$1)$

r$2=$ bt$2.$add$\_$right$(6,$ l$1)$

l$3=$ bt$2.$add$\_$left$(7,$ l$2)$

r$3=$ bt$2.$add$\_$right$(4,$ l$2)$

bt$2.$add$\_$left$(1,$ l$3)$

bt$2.$add$\_$right$(7,$ l$3)$

print$("$Height of bt$1$:$",$ bt$1.$height$())$

print$("$Count of $7$ in bt$1$:$",$ bt$1.$countK$(7))$

print$("$Are bt$1$ and bt$2$ equal?", bt$1.$equal$($bt$2))$

# Making bt$2$ different from bt$1$

bt$2.$add$\_$left$(100,$ l$3)$

print$("$Are bt$1$ and bt$2$ equal after modification?", bt$1.$equal$($bt$2))$