BST Paths and LCA

This problem involves constructing and traversing binary search trees.

Definitions

Path: A path in a tree t to a node with value n is the sequence of node values encountered as we go from the root of t to the node with value n. For this problem we represent paths using Python lists (i.e., arrays); if a path does not exist (e.g., because the node specified is not in the tree), we indicate this using None.

Example: see image.

A path from the root of a tree to a node n in a tree begins at the root node of the tree and ends at node n. Thus, in the example above, [3, 1, 2] is not a path from the root to node 2 because it does not begin with the value of the root node (= 6). [6, 3, 1, 2] is not a path to the node 1 because it does not end with 1.

Ancestor: A node m is an ancestor of a node n in a tree if either of the following hold:

1. m is the same as n; or
2. m is higher in the tree than n (i.e., closer to the root); and there is a path from m to n .

Thus, in the example above, 3 is an ancestor of 1. However, 8 is not an ancestor of 1 because there is no path from 8 to 1. 2 is not an ancestor of 1 because 2 is not higher up in the tree than 1.

Lowest common ancestor: A node k is a common ancestor of two nodes m and n if k is an ancestor of both m and n. k is the lowest common ancestor of m and n if it is the lowest node in the tree (i.e., farthest from the root) that is a common ancestor of m and n.

To compute the lowest common ancestor of two nodes m and n in a tree, we compare the paths to m and n to see which nodes they have in common. Each node that occurs in both paths is a common ancestor to m and n , and the lowest common ancestor is the last (i.e., lowest) of these. Note that, as defined above, a node is its own ancestor, which means that if m == n then the lowest common ancestor is m.

Program Behavior

In a file bst.py implement a program that implements the following binary search tree functionality a specified below:

A TreeNode class for binary search tree nodes, as specified below under 2.2.2. Programming Requirements.

The following functions (outside the TreeNode class):

• mktree(node_list)
  This function takes as argument a Python list (i.e., array) node_list and returns the binary search tree created by inserting the values in node_list in the order they appear. If node_list == [] the tree constructed is None (i.e., the empty tree).

• insert(tree, val)
  tree is a binary search tree (which may be empty, i.e., None), val is a value at a tree node. This function returns the tree resulting from inserting val into tree.

• path(tree, val)
  tree is a binary search tree (which may be empty, i.e., None), val is a value at a tree node. Returns a Python list that gives the path (i.e., sequence of values) from the root of tree to the node with value val, if such a path exists; None otherwise.

• lca(tree, val1, val2)
  This function computes the lowest common ancestor of two nodes in a binary search tree. Given a TreeNode object tree that is the root of a binary search tree, and values val1 and val2, lca(tree, val1, val2) should behave as follows:
  • if val1 and val2 appear in tree (i.e., there are nodes in tree with values val1 and val2), it should return the value at the node that is the lowest common ancestor of the nodes with values val1 and val2 (see below).
  • if either val1 or val2 is not in tree it should return None.

Programming Requirements

The insert() and path() methods for the TreeNode class, as well as the functions insert(), path(), and lca() should be implemented using recursion; they should not use loops or constructs with loop-like behavior, e.g., list comprehensions. The mktree(node_list) function can use a loop to iterate over the values in the argument node_list.

The methods for the TreeNode class (except possibly for __str__() if you decide to implement it) should not use other data structures such as Python lists or dictionaries.

1.The TreeNode class
The TreeNode class should implement attributes sufficient to represent a binary search tree node, as discussed in class. The names you choose for these attributes should be descriptive and should be chosen to indicate that the attributes are not public. Values stored in TreeNode objects can be anything that can be compared to other similar values using <, <=, >, >=, etc. Thus, they may be numbers, or strings, or any other type that supports such comparison operations. Your code should not make assumptions about these values beyond their ability to support such comparison operations. The TreeNode class should also implement the following methods (you can additionally implement other helper methods if you want):

• insert(self, n) : n is a value. Inserts n into the binary search tree rooted at this TreeNode object, returns the resulting tree.
• path(self, n) : n is a value. Returns a Python list that gives the path from this node to the node with value n. If the value n is not found in the tree or if there is no path from this node to node n, the value returned should be None. This method should not change the tree in any way.

2.The functions insert(), path(), and lca()
The functions insert(), path() and lca(), as well as any helper functions used by any of these functions, should be implemented using recursion. The functions path() and lca() should not modify the tree provided as argument.

Invoking your code

Here is the conceptual structure of how your code will be invoked by the tester:

val_list = … construct a list of values …

# e.g., maybe using input() and split()
# construct the tree
tree = mktree(val_list)
val0 = some value

# e.g., maybe using input()
val1 = some value

# e.g., maybe using input()
val2 = some value

# e.g., maybe using input()
print( tree.path(val0) )
print( lca(tree, val1, val2) )

Examples

Program runs: see image.