Binary Tree as a List

The Binary Tree Abstract Data Type (ADT) has the following description of methods:

• BinaryTree() constructs a binary tree with no children
• get_root_val() returns the root value of this particular sub-tree
• set_root_val(val) modifies the root value of this particular sub-tree
• get_left_child() returns the subtree that is the left child of the current root
• get_right_child() returns the subtree that is the right child of the current root
• insert_left(val) creates a new binary tree and installs it as the left child of the current node, moving the current child down one level in the tree
• insert_right(val) creates a new binary tree and installs it as the right child of the current node, moving the current child down one level in the tree

This ADT can be implemented in a number of ways. In this exercise we'll implement a Binary Tree using a Python list.

Write a list-based representation of a Binary Tree in a program called binary_tree_list.py where a tree is represented by a three-element list:

r = [ value,  [ left_child ],  [ right_child ]]

The left_child and right_child values refer to subtrees that may have their own values and children.

Use the following Python function headers in your list-based implementation:

def binary_tree(val)
def get_root_val(root)
def set_root_val(root, new_val)
def get_left_child(root)
def get_right_child(root)
def insert_left(root, new_branch)
def insert_right(root, new_branch)

Once you've written your tree-based implementation of the Binary Tree you can use the following code to test it.

def main():
    t = binary_tree(3)
    print("Instruction: t = binary_tree(3)")
    print("Result:", t)
    print("Expect: [3, [], []]")
    insert_left(t, 4)
    print("Instruction: insert_left(t, 4)")
    print("Result:", t)
    print("Expect: [3, [4, [], []], []]")
    insert_left(t, 5)
    print("Instruction: insert_left(t, 5)")
    print("Result:", t)
    print("Expect: [3, [5, [4, [], []], []], []]")
    insert_right(t, 6)
    print("Instruction: insert_right(t, 6)")
    print("Result:", t)
    print("Expect: [3, [5, [4, [], []], []], [6, [], []]]")
    insert_right(t, 7)
    print("Instruction: insert_right(t, 7)")
    print("Result:", t) 
    print("Expect: [3, [5, [4, [], []], []], [7, [], [6, [], []]]]")
    l = get_left_child(t)
    print("Instruction: l = get_left_child(t)")
    print("Result: l =", l)
    print("Expect: l = [5, [4, [], []], []]")
    set_root_val(l, 9)
    print("Instruction: set_root_val(l, 9)")
    print("Result: l =", l)
    print("Expect: l = [9, [4, [], []], []]")
    insert_left(l, 11)
    print("Instruction: insert_left(l, 11)")
    print("Result:", t)
    print("Expect: [3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]")
    print("Instruction: print(get_right_child(get_right_child(t)))")
    print("Result:", get_right_child(get_right_child(t)))
    print("Expect: [6, [], []]")    

if __name__ == "__main__":
    main()