CODEWITHSUNDEEP
pythonpython-3.xtreebinary-treepostorder
Nick
Nick

Reputation: 137

Creating perfect binary trees with postorder traversal

I'm trying to build a perfect binary tree at h height using postorder traversal. Basically I'm trying to do this:

height = 3
numbers = list(range(1, 2 ** height))
tree = buildTree(height, numbers)

The result would be something like this:

   7
 3   6
1 2 4 5

I'm not really too worried about printing it out in the tree structure. I'm just trying to build the tree correctly. My code is very simple, but I'm having trouble finding out what is wrong with it.

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

def postorder(height, numbers):
    if height == 1:
        return Node(numbers.pop())
    node = Node()
    node.left = postorder(height-1, numbers)
    node.right = postorder(height-1, numbers)
    node.root = numbers.pop()
    return node

Upvotes: 4

Views: 2271

Answers (1)

Nick
Nick

Reputation: 137

I ended up figuring it out. The only way to do this is to fill the tree right to left, and decrement the numbers as you recurse. I was trying to fill from left to right.

def postorder(height, nums):
    if h == 1:
        return Node(nums.pop())
    node = Node()
    node.root = nums.pop()
    node.right = postorder(height-1, nums)
    node.left = postorder(height-1, nums)
    return node

height = 3
tree = postorder(height, list(range(1, 2 ** height)))

It may be worth noting what is going on since it was confusing me a little. A perfect tree has k elements where k = (2^height) -1. list(range(1, 2 ** height)) creates the list of values since the stopping point on range is exclusive. There is no need to reverse the list for building right to left because pop() removes the last element from the list. I was building left to right and filling in the largest elements first.

This is being built.      It is being built in this order.
      7                                1
    3   6                            5   2
   1 2 4 5                          7 6 4 3

Upvotes: 3

Related Questions