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

Question

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:

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

Patrick Haugh · Accepted Answer · 2018-01-28T05:25:56.743

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

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

Niema Moshiri · Answer 2 · 2018-01-28T05:24:22.247

0

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)

edited Jan 28 '18 at 05:24

answered Jan 28 '18 at 05:17

Niema Moshiri

909
5
14

I'd recommend against using `queue.Queue` if you just want a normal data structure. That class is intended for synchronized communication between threads (it has locks, etc., which you don't need). Instead, use `collections.deque` (pronounced deck, and officially meaning double-ended-queue), which has only the stuff you need. The `queue.Queue` class uses a `deque` internally! – Blckknght Jan 28 '18 at 05:27

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

2 Answers2