How to pass by reference while building trees?

Question

I want to create an object, lets call it a model, which includes an attribute, the root of a binary tree. I want that model object to have a method which builds a binary tree of a specific depth.

I created such a class, model, which uses a tree node class binary_tree_node, both shown below:

class binary_tree_node:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None

class model:
    def __init__(self, max_depth = 3):
        self.root = None
        self.max_depth = max_depth

    def build_tree(self):
        self.build_tree_recursive_helper(self.root, 0)

    def build_tree_recursive_helper(self, node, current_depth):
        # create the new node
        node = binary_tree_node('data')

        # check base case
        if current_depth >= self.max_depth:
            return

        # make recursive calls
        self.build_tree_recursive_helper(node.left_child, current_depth + 1)
        self.build_tree_recursive_helper(node.right_child, current_depth + 1)

I expect to be able to instantiate the model, build the tree, then introspect the tree, like so

m = model()
m.build_tree()
print(m.root.data)
>>> 'data'

But instead I get the following upon trying to introspect:

m = model()
m.build_tree()
print(m.root.data)

AttributeError                            Traceback (most recent call last)
<ipython-input-138-eaa2b3c07e85> in <module>
      1 m = model()
      2 m.build_tree()
----> 3 print(m.root.data)

AttributeError: 'NoneType' object has no attribute 'data'

This violates my understanding that python passes object references and not values.

How should I modify my binary_tree_node and model classes to achieve my intended results?

Read this: Why can a function modify some arguments as perceived by the caller, but not others? — Aran-Fey
– Aran-Fey, Commented Mar 28, 2019 at 21:54
You basically have to rewrite the recursive method so that instead of assigning something to node and then recursively populating that node's children, it recursively creates a node + children and returns it, and then you assign that return value to self.root. — Aran-Fey
– Aran-Fey, Commented Mar 28, 2019 at 21:56
Python does not support call by reference semantics. The only evaluation strategy supported is "call by sharing", better known as call-by-assignment. The problem here is that your build_tree method does nothing to the nodes it builds, they are simply discarded. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Mar 28, 2019 at 22:12
Note, python doesn't distinguish between "references and values". There is a common misunderstanding that passing a reference means "call by reference". This is incorrect. C only supports call by value. But you can, of course, pass references (pointers) as arguments. The distinguishing feature in call by reference is that assignments to that parameter in the function are seen in the caller. So imagine we had call by reference in Python along with it's normal strategy and we used & to signify such a parameter, def Foo(&x): x = 42; a = 0; Foo(a); print(a) would print 42. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Mar 28, 2019 at 22:24

dcg · Accepted Answer · 2019-03-28 21:58:47Z

2

Why instead don't return the node built and get the reference, something like the next:

max_depth = 4

def build_tree_recursive_helper(current_depth): 
    # check base case
    if current_depth >= max_depth:
        return None 

    node = binary_tree_node('data')

    # make recursive calls
    node.left_child = build_tree_recursive_helper(current_depth + 1)
    node.right_child = build_tree_recursive_helper(current_depth + 1)

    return node

Note that you have to put the self back in your implementation.

answered Mar 28, 2019 at 21:58

dcg

4,2291 gold badge26 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to pass by reference while building trees?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related