Recursive Insert using Python

Question

I am having a bit of a hard time with a recursive insert function that I been studying through zybooks data structures.I didn't have any issues with a normal insert but with the recursive it is confusing me a lot. The function is gathering the tree information as a parameter. The keys are the names which are all unique. I haven't inserted anything in the parameter to put in the function in the else statement. Would appreciate some pointers if possible.

class Star:

    def __init__(self, hvg_db, name, mag, spectral, habit, dist):
        self.hvg_db = hvg_db 
        self.display_name = name  #
        self.magnitude = mag 
        self.spectral_class = spectral  
        self.habitable = habit  #
        self.distance_parsecs = dist 

class TreeNode:
    def __init__(self, star):
        self.left = None
        self.right = None
        self.star_info = star
        self.name = "N" + str(self.star_info.hvg_db)
        self.key = star.display_name

class Tree:
    def __init__(self, name):
        self.name = name
        self.node_num = 0
        self.node_list = []
        self.root = None

       def insert_rec(self, star):  # method receives star info (star, magnitude, habitable, etc

        star = TreeNode(star)

        if self.root is None:
            self.root = star
            print("Parent Activated")

        parent = self.root

        if star.key < parent.key:
            if parent.left is None:
                print("Left is Empty")
                parent.left = star
            else:
                print("Else Left")
                self.insert_rec(star)

            if parent.right is None:
                print("Right is Empty")
                parent.right = star
            else:
                print("Else Right")
                self.insert_rec(star)
def main():
    # Instantiate Binary Tree to hold the stars
    star_tree = Tree("Star Catalog")

    with open('HabHYG_short.csv', 'r') as csvfile:
        lines = csv.reader(csvfile, delimiter=',')

        # skip header row
        next(csvfile)

        # get time in nanoseconds -- maybe OS-specific?
        # See https://docs.python.org/3/library/time.html

        t0 = time.perf_counter_ns()

        obs_processed = 0

        for row in lines:
            # hvg_db, name, mag, spectral, habit, dist)
            this_star = Star(row[0], row[3], row[16], row[11], row[2], row[12])
            star_tree.insert_rec(this_star)
            

Answer 1

A nice way to handle recursive operations in an object-oriented tree structure is to implement them in the nodes themselves. Create an insert method of TreeNode that recursively inserts a new node somewhere underneath that node. This only requires two decisions:

1. Is the new node going somewhere in my left or right subtree?
2. Does the subtree already exist (in which case we want to insert it underneath that node) or am I creating it?

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def insert(self, node):
        if node.key < self.key:
            # Insert in left subtree, or create it.
            if self.left:
                self.left.insert(node)
            else:
                self.left = node
        else:
            # Insert in right subtree, or create it.
            if self.right:
                self.right.insert(node)
            else:
                self.right = node

Then you can build a tree by doing something like:

root = TreeNode(5)
root.insert(TreeNode(3))
root.insert(TreeNode(8))
root.insert(TreeNode(1))
root.insert(TreeNode(4))
root.insert(TreeNode(6))
root.insert(TreeNode(9))

which builds a tree like:

                  5
                /   \
               3     8
              / \   / \
             1   4 6   9

Writing a function that'll print out a nice tree representation like that is left as an exercise to the reader, but it's easy to mess around with it in the REPL:

>>> from test import *
>>> root.left.left.key
1
>>> root.key
5
>>> root.right.key
8
>>> root.right.right.key
9

The idea of recursion is that you don't need to write a loop that traverses the tree; all you need to do is figure out whether you (the self that insert was called on) know exactly where the new node needs to go, or if you need to hand it off to another node (one of your subtrees) to figure out.

The iteration happens implicitly as each node calls the next one in the chain. Each recursive call just needs to move the execution flow one step closer to where it needs to get.