CODEWITHSUNDEEP
pythontreebinary-treepostorder
user7622302
user7622302

Reputation:

Python Number nodes in postorder

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)

Upvotes: 1

Views: 988

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

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)

Upvotes: 1

Kirill Bulygin
Kirill Bulygin

Reputation: 3826

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

Upvotes: 1

Related Questions