0

I am trying to figure out the best way of coding a Node Class (to be used in a binary tree) that would contain the attributes key, left and right.

I thought I would do something like

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

and then do

a = Node('A')
b = Node('B') 
c = Node('C')   
a.left = b
a.right = c

Here I am a little bit confused: are (under the hood) left and right pointers? Or is a containing a copy of the whole tree?

If I add

d = Node('B') # same key as before, but an entirely different node
c.right = d

then are b and d two different objects even if they have the same attributes? I would think so because they don't share any memory.

Finally, if I want to do a deep copy of one of my nodes, is

e = Node(a.key))

sufficient?

Improve this question
6
  • Yes, left and right are references. You can think of this connection as the branch that binds two nodes together. Commented Feb 12, 2015 at 13:59
  • @meto: Thus every node has a maximum of two edges? Commented Feb 12, 2015 at 14:02
  • @CommuSoft Yes let's assume that is a binary tree. If now, I could use an attribute called children that is a list of nodes, which should't change the essence of my question, I believe. Commented Feb 12, 2015 at 14:05
  • @Meto: that's not guaranteed to be a tree since you can state a.left = b and b.right = a creating a loop which is not allowed in a tree. Commented Feb 12, 2015 at 14:07
  • If you want a new copy rather than a reference, you can use the copy module in the standard library. Commented Feb 12, 2015 at 14:12

3 Answers 3

Reset to default
3

Python is dynamically typed, so you can't say left and right are references. One can also store an integer, or float in them. You can even first store an integer then a reference to an object and later a float in them, so the type might vary over time. But if you perform an assignment to an object. That will indeed result in a pointer (this is a huge semantical difference with your question).

For your second question, it depends on how you see deep copying. If your node contains references to other nodes, do you want to copy these nodes as well?

If you are interested only in generating a new node with the same value but with references to the same other nodes, then use: copy.copy, otherwise use copy.deepcopy.

The difference is:

B <- A -> C       B' <- D -> C'
^         ^
|         |
 \-- S --/

With S a shallow copy and D a deep copy. Note that a deep copy thus results in new nodes B' and C'. You can imagine that if you deep copy a huge tree this can result in a large memory and CPU footprint.

Your code

e = Node(a.key))

Is not completely correct since you don't copy (potential) references to your left and right node, and furthermore it's not good design since you can attach more items to the node and you need to modify your copy function(s) each time. Using the copy.copy-functions is thus more safe.

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

Comments

2

Yes b and d have the same attributes, but they are two independent instances. To see this:

print id(b) # one number
print id(d) # new number

This proves that they are two different objects in memory. To see that a.right is the same object as c use the same technique, checking for equivalent id values.

print id(a.right)
print id(c) # same
Improve this answer

Comments

0

Yes these are just references to the left or right object. Everytime you do Node("some_str), a new object is created. So b & d will be different, and a new object gets created for e = Node(a.key)). Doing a e = Node('E') and doing f = e will be the same, with f and e referring to the same object.

Improve this answer

2 Comments

I hope this wasn't downvoted just because of the term "pointer". To me, the term "reference" and "pointer" are basically interchangeable, and every name in Python is a reference! Even "containers" in Python are just collections of references. Some of the punctuation and wording could be cleaned up a bit (there are mismatched quotes and parens, and the last sentence is a bit unclear), but otherwise, I don't see what's wrong with this answer.
Didn't downvote. But there are huge differences between pointers and references. A pointer points to an address in memory whereas a reference points to a record/object. If one has a memory-managed environment (garbage collector) objects can be moved and references are modified. A pointer has no real interpretation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.