Search code examples
javatreebinary-search-treetraversal

Binary tree traversal with level

is there any kind of way to traverse the tree, which would allow me to print out the binary tree WITH the level of each node ? So let's say I have this tree:

   10
   /\
  5  15
 /    /\
2    12 16

And the output (in preorder for example) would be:

node (level)

10 (0), 5 (1), 2 (2), 15 (1), 12 (2), 16 (2)

the most ideal way would be with binary way:

10 ([]), 5 ([1]), 2 ([11]), 15 ([0]), 12 ([01]), 16 ([00])

Solution

  • Yeah, that's definitely possible. It looks like you want to traverse the tree in depth first order which makes things nice and simple.

    The algorithm will look something like this (in pseudocode since no code provided for reference):

    void traverse(node, depth) {
  print(node.value, depth);
  depth++;
  traverse(node.leftChild, depth);
  traverse(node.rightChild, depth);
  depth--;
}

    So you just call that method passing in the root node of the tree and the initial depth (0).