Binary Search Tree

The Node class and the BST class header are given. Write the rest of a binary search tree: insert(value) adds a value, going left of a node when the value is smaller and right when it is larger, and ignoring a value already in the tree; contains(value) returns whether a value is in the tree by walking down from the root with a while loop over a current node; in_order() returns a list of every value in ascending order, because an in-order walk (left subtree, the node itself, right subtree) of a BST visits the values sorted. Recursion is the natural tool for insertion and the walk: write helper functions insert_node(node, value) returning the node (a new one when node is None) and collect_in_order(node, result) that appends into a list. Do NOT write a main block or any top-level test code; the tests construct the class. Input: two lines, the values to insert in order (possibly empty) and then the values to look up; the tests print the in-order list, then one boolean per lookup.