Binary Tree: How Do Class Instances Link?

Question

I am trying to understand binary trees, but doing so has brought me to confusion about how class instances interact, how does each instance link to another?

My Implementation:

class Node(object):
    def __init__(self, key):
        self.key= key
        self.L  = None
        self.R  = None



class BinaryTree(object):
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    def insert(self, key):
        if self.get_root()==None:
            self.root = Node(key)
        else:
            self._insert(key, self.root)

    def _insert(self, key, node):
        if key < node.key:
            if node.L == None:
                node.L = key
            else: 
                self._insert(key, Node(node.L))
        if key > node.key:
            if node.R == None:
                node.R = key
            else: 
                self._insert(key, Node(node.R))

myTree= BinaryTree()

A Scenario

So lets say I want to insert 10, I do myTree.insert(10) and this will instantiate a new instance of Node(), this is clear to me.

Now I want to add 11, I would expect this to become the right node of the root node; i.e it will be stored in the attribute R of the root node Node().

Now here comes the part I don't understand. When I add 12, it should become the child of the root nodes right child. In my code this creates a new instance of Node() where 11 should the be key and 12 should be R.

So my question is 2-fold: what happens to the last instance of Node()? Is it deleted if not how do I access it?

Or is the structure of a binary tree to abstract to think of each Node() connected together like in a graph

NB: this implementation is heavily derived from djra's implementation from this question How to Implement a Binary Tree?

MatTheWhale · Accepted Answer · 2017-08-09T20:07:14.017

Make L and R Nodes instead of ints. You can do this by changing the parts of your _insert function from this:

if node.L == None:
    node.L = key

to this:

if node.L == None:
    node.L = Node(key)

There is also a problem with this line:

self._insert(key, Node(node.L))

The way you're doing it right now, there is no way to access that last reference of Node() because your _insert function inserted it under an anonymously constructed node that has no parent node, and therefore is not a part of your tree. That node being passed in to your insert function is not the L or R of any other node in the tree, so you're not actually adding anything to the tree with this.

Now that we changed the Ls and Rs to be Nodes, you have a way to pass in a node that's part of the tree into the insert function:

self._insert(key, node.L)

Now you're passing the node's left child into the recursive insert, which by the looks of thing is what you were originally trying to do.

Once you make these changes in your code for both the L and R insert cases you can get to the last instance of Node() in your

example tree via myTree.root.R.R. You can get its key via myTree.root.R.R.key, which equals 12.

Thanks for expanding on your original post; just to be certain, the identity of the `node` that is the rightmost would be myTree.root.R.R*(n-2).key? — Artemis, Aug 09 '17 at 20:47
You could use recursion to find the rightmost node, similar to what you did for insertion. You could define a function that takes in a node and either returns the node's key if its `R` is `None`, or makes a recursive function call passing in the node's `R` if the node's `R` is not `None`. Then, when you call this function passing in the root node, the function will go to the root's right child, then the root's right child's right child, and so on until it can't go right anymore, at which point it returns the key of the rightmost node — MatTheWhale, Aug 09 '17 at 21:17

score 1 · Answer 2 · answered Aug 09 '17 at 19:50

Most of you're questions come from not finishing the program; In your current code after myTree.insert(11) you're tree is setting R equal to a int rather than another Node.

If the value isn't found then create the new node at that point. Otherwise pass the next node into the recursive function to keep moving further down the tree.

def _insert(self, key, node):
    if key < node.key:
        if node.L == None:
            node.L = Node(key)
        else: 
            self._insert(key, node.L)
    if key > node.key:
        if node.R == None:
            node.R = Node(key)
        else: 
            self._insert(key, node.R)

P.S. This isn't finished you're going to need another level of logic testing incase something is bigger than the current Node.key but smaller than the next Node.

Binary Tree: How Do Class Instances Link?

My Implementation:

A Scenario

2 Answers2