Question $2.[25$ marks$]$

Write the pseudo code of a non$-$recursive algorithm BST$\_$Search$\_$non$\_$recursive$($Node root, int $\backslash ($ k $\backslash ))$ to search a key value $\backslash ($ k $\backslash )$ in a binary search tree with root node. If $\backslash ($ k $\backslash )$ is found in the binary search tree, return the node containing it; otherwise, return NIL. A node is defined as follows.

class Node $\backslash \{$

int key;

Node$*$ parent;

Node$*$ left;

Node$*$ right;

$\backslash \}$

Answer:

BST$\_$Search$\_$non$\_$recursive$($Node root, int $\backslash ($ k $\backslash ))\backslash (\backslash \{\backslash )$