Creating a binary tree through a loop

Question

I want to create a binary tree by iterating through a loop. I know how to write a very basic binary tree.

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None


root = Tree()
root.data = 75
root.left = Tree()
root.left.data = 95
root.right = Tree()
root.right.data = 64

root.left.left = Tree()
root.left.left.data = 32
root.left.right = Tree()
root.left.right.data = 93
root.left.left = Tree()
root.right.left.data = 32
root.left.right = Tree()
root.right.right.data = 93

print(root.data)

This is tedious handtyping it, and if I were to have a list of numbers:

list = [1,2,3,4,5,6,7]

and put it through a loop to create a binary tree in this order so:

   1 
 2   3
4 5 6 7

How would I write that? and because I'm using this to calculate the sum of all the paths, how do you navigate/iterate through a binary tree:

Related to this. Not a complete dup though because the OP wants to automate the process of creating the tree. — Chris
– Chris, Commented Jul 4, 2017 at 0:05
@juanpa.arrivillaga Sorry, I dont understand what a node is. I am very new to binary trees. — user5676791
– user5676791, Commented Jul 4, 2017 at 0:10

randomir · Accepted Answer · 2017-07-04 00:47:55Z

7

To build a full binary tree (not necessarily a binary search tree) from a list of node values, let's assume values in the list are ordered according to level-order traversal. So, a list from your question

values = [1,2,3,4,5,6,7]

will represent a tree:

   1 
 2   3
4 5 6 7

Notice that the root value is at the position 0, its left child is at the position 1*2-1=1, the right child at 1*2=2, etc. In general for a node in the list at index i, its left child is at position (i+1)*2-1, and the right child at (i+1)*2.

Now, we simply need to build the tree recursively, node by node, at each step creating the left and the right subtree.

To make it simpler, let's assume the list of values is global.

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

def buildTree(i):
    if i < len(values):
        return Node(values[i], left=buildTree((i+1)*2-1), right=buildTree((i+1)*2))

values = [1,2,3,4,5,6,7]
tree = buildTree(0)

To print-out the tree, we can use the preorder tree traversal:

def preorder(node):
    if node is None:
        return
    yield node.data
    for v in preorder(node.left):
        yield v
    for v in preorder(node.right):
        yield v

Like this:

>>> print list(preorder(tree))
[1, 2, 4, 5, 3, 6, 7]

edited Jul 4, 2017 at 0:47

answered Jul 4, 2017 at 0:32

randomir

18.8k1 gold badge46 silver badges60 bronze badges

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

2 Comments

user5676791 Over a year ago

If I were to have node 5 be shared by 2 and 3 how would I do that?

randomir Over a year ago

Can you give me an example of what do you mean by that? If you want a node (5) to have two parents (2 and 3 above), then you need a general graph, not tree (which is a special type of graph).

Collectives™ on Stack Overflow

Creating a binary tree through a loop

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related