CODEWITHSUNDEEP
pythonpython-3.xbinary-tree
Alex Helvaty
Alex Helvaty

Reputation: 57

Printing Binary Tree in Level Order without Left or Right in Python

This question is seeking an alternative to the answers given in this post.

How can I create a string which has each level of the tree on a new line with the following Binary Tree Structure:

# A Node is an object
# - value : Number
# - children : List of Nodes
class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

My problem is that I'm used to Tree Structures like this:

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

Here is an example tree:

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

That would print as:

1 
23
4
56
7

Any help or ideas on how to create a definition using that new structure would be very appreciated.

Upvotes: 0

Views: 528

Answers (2)

Patrick Haugh
Patrick Haugh

Reputation: 60994

You can just use list.extendto add child nodes instead of appending them one by one.

class Node:
  def __init__(self, value, children):
    self.value = value
    self.children = children


def traverse(root):
  curr = [root]
  while curr:
    next_level = []
    for n in curr:
      print(n.value, end='')
      next_level.extend(n.children)
    print()
    curr = next_level

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

traverse(exampleTree)

prints

1
23
4
56
7

(For anyone who didn't read the question, this is entirely derivative of this answer)

Upvotes: 1

Niema Moshiri
Niema Moshiri

Reputation: 937

You could use a queue to perform a BFS on your tree:

try:
    from queue import Queue # Python 3
except ImportError:
    from Queue import Queue # Python 2
q = Queue() # create new queue
q.put(root) # where "root" is the root node of the tree
while not q.empty():
    curr = q.get() # get next node from queue
    print(curr.value) # get node's value
    for child in curr.children:
        q.put(child) # add each child to the queue

Note that this solution works for all trees, not just binary

EDIT: Sorry, didn't realize that you wanted all the ones in the same level to be in the same line of output. Use the other solution (or modify mine appropriately)

Upvotes: 0

Related Questions