1

I have a binary tree with nodes like shown below.

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

Given a tree, I want to number it from 0 in post order. An example of what I want to do

>>> left = Node(None, Node(3), Node(2))
>>> right = Node(None, Node(9), Node(10))
>>> node = Node(None, left, right)
>>> number(node)
>>> tree.left.number, tree.right.number, tree.number
0, 1, 2

However, I'm having trouble getting the right cases for the recursion part.

I am trying something like 

def number(node, count=0):
    if not node.left and not node.right:
        node.number = count
        count += 1
    else:
        number(node.left, count)
        number(node.right, count)
Improve this question
6
  • What is the problem? I suggest adding print statements to your code to see what is happening. Commented Feb 25, 2017 at 16:46
  • What is the difference between value and number? Commented Feb 25, 2017 at 16:47
  • 1
    Does your code even compile? Node(3) should give an error. Commented Feb 25, 2017 at 16:47
  • Be sure to read my first comment. Commented Feb 25, 2017 at 16:53
  • @user7622302: you also introduce a HuffmanNode which you did not define. You perhaps better use Node such that the code compiles. Commented Feb 25, 2017 at 16:58

2 Answers 2

Reset to default
1

There are several problems with your code:

  • you do not set the number in the else case;
  • you do not make implement logic when the tree has one child; and
  • you do not keep track how much the counter is incremented.

You can solve these issues by returning the count value after you have assigned numbers. So something like:

def number(tree, count=0):
    # ...
    return new_count

Now the problem is how to assign numbers to the tree and its children. You can do this by first inspecting the left child. If it is not None, you call number(..) recursively on tree.left and store the returning count. Next you inspect the right child and do the same thing. Finally you assign the updated count to the tree itself and return the result. So something like:

def number(tree, count=0):
    if tree.left is not None:
        count = number(tree.left,count)
    if tree.right is not None:
        count = number(tree.right,count)
    tree.number = count
    return count+1

Running this in the console:

>>> leftleft = Node(3)
>>> leftright = Node(2)
>>> left = Node(None,leftleft,leftright)
>>> rightleft = Node(9)
>>> rightright = Node(10)
>>> right = Node(None,rightleft,rightright)
>>> node = Node(None, left, right)
>>> number(node)
7
>>> left.number,right.number,node.number
(2, 5, 6)
>>> leftleft.number,leftright.number,left.number,rightleft.number,rightright.number,right.number,node.number
(0, 1, 2, 3, 4, 5, 6)
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

@KirillBulygin: I think you miss the count = ... part. You thus update the count. Ans the count is guaranteed to be incremented with 1 since it returns count+1: the assignment of the last number. You can check it.
"you do not keep track how much the counter is incremented." This is key.
@user7622302: in your tree, you constructed a tree with five nodes...
@user7622302: see updated answer. left has number 2 since it has two children that are enumerated first in postfix notation.
1

There are at least two problems:

  • You number only leaf nodes.
  • count is a number, it can't be changed "by reference".

I'd suggest something like this (as a general idea):

def number(tree, count=0):
    node.number = count
    count += 1
    if node.left:
        count = number(node.left, count) + 1
    if node.right:
        count = number(node.right, count) + 1
    return count
Improve this answer

3 Comments

That's preorder.
@WillemVanOnsem That's a general idea to illustrate the problems described.
"count is a number, it can't be changed "by reference"." This by far the biggest problem.

Your Answer

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