csc148_slog_binary_search_tree

    In week 8, we learned something about binary search tree and the implementation of some methods of BST such as insert,delete(in lecture), count_less(in lab), __contains, max_node(in exercise).
    The basic idea to implement insert and delete is to use recursion. The algorithm of delete is comparably more difficult because when we delete a node(when data == node.data), we have to make it replaced by another node which doesn't break the rule of BST. Here we want want to find the max node of left sub-node(or min node of right sub-node) and use it to replace the deleted node.
    Another challenging topic in this week is the conversion from recursive algorithm to iterative algorithm. Actually, we can find the corresponding iterative algorithm for every recursive algorithm if we have pondered the essence of the recursion. Here I take Fibonacci sequence as example: the basic idea of the recursive algorithm is showed in the picture below.
 

 












   
    Here we can code in iteration but using the idea of recursion.(We can see that recursion is just like popping a element from a stack, make some calculation, and put back the recursion function into the stack, and do it over and over again until the stack is empty)


def function(x):
    c = 0
    stack = [x]
    while stack:
        p = stack.pop()
        if p > 1:
            stack.append(p - 1)
            stack.append(p - 2)
        elif p == 1:
            c = c + 1      
    return c