-2

I have done a lot of research on how to traverse through binary trees and I still have not found a way to traverse through a tree without going all the way to its leaves. I just want to print the binary tree one level at a time instead of using In-Order-Traversal, Pre-Order-Traversal, or Post-Order-Traversal results.

I want to print: {2, 7, 5, 2, 6, null, 9, null, null, 5, 11, 4, null}. Can I use recursion to solve this? Because it seems like I always end up at the leaves of one side before I solve for the other sides non-leaves.

enter image description here

Community
  • 1
  • 1
Kousei
  • 25
  • 4
  • 1
    The key phrase here is "breadth first", *if* you go to the leafs first it is called "depth first". Google for how to implement "breadth first". – luk2302 Dec 29 '17 at 23:24
  • What you want won't be a typical binary tree traversal, since traversing is recursive way of visiting (root - leftChild - rightChild), (leftChild - root - rightChild), (leftChild - rightChild - root). And you see that there are no other possibilities there. – Dimitar Dec 29 '17 at 23:27

1 Answers1

-1

In pseudo code:

  • Create a queue of nodes (A Deque in java, eg LinkedList)
  • Put the root node on the queue
  • While the queue is not empty
    • Take the next node from the head
    • put its children on the end of the queue
    • process the node

Basically, to process breadth first (which is what you want), use a queue. To process depth first, use a stack

Bohemian
  • 412,405
  • 93
  • 575
  • 722