Homework: binary tree - level-order trasversal

Question

hi, is there a way to visit a binary tree from the lowest level to the higher (root) ?

not from the root-level to the lowest!!!

(and not using the level-order traversal and a stack...!!!) <--- its opposite..

so difficult...thank you!

Answer 1

Provided I understood you question correctly: If you want to traverse the tree visiting a leaf first and the root last, you can visit the nodes on the way back as you traverse the tree.

function traverse(node)
    for each child of node
        traverse(child)
    end
    visit(node)
end

If you want to visit the nodes in level order, you could do something like this (though using a stack -- I'm not sure whether you didn't want one at all or some particular solution using a stack):

queue.push(root)
while queue is not empty
    node = queue.pop()
    for each child of node
        queue.push(child)
        stack.push(child)
    end
end
while stack is not empty
    visit(stack.pop())
end

You can do it using only a queue, but with worse time complexity, if you do it like this:

for i = treedepth down to 0
    queue.push(root)
    while queue is not empty
        node = queue.pop()
        if node has depth i
            visit(node)
        else
            for each child of node
                queue.push(child)
            end
        end
    end
end

The tree depth and node levels can be found using an initial traversal, if needed.

However, if you are allowed to make recursive calls, you actually have access to a stack (the call stack). This can be exploited to implement the second solution, but making the stack implicit.

function unwind(queue)
    if queue is not empty
        node = queue.pop()
        unwind(queue)
        visit(node)
    end
end

queue.push(root)
while queue is not empty
    node = queue.pop()
    for each child of node
        queue.push(child)
        queue2.push(child)
    end
end

unwind(queue2)

And of course, if you have access to almost any other data structure (list, array, priority queue, double ended queue, etc.) you can easily implement a stack yourself. But then it would be rather pointless to forbid stacks in the first place.

Answer 2

You probably could do it easily IF you maintained a pointer to the node at the greatest depth. If you don't, then you must find that node before begining your traversal. Also, your nodes will all have to have pointers to their parents.

Answer 3

There's a few challenges here that lead to different solutions:

1. Can you traverse up the tree? Often data structures are set up so you can only go down. You could find all leaf nodes, put them in a priority queue by level, and then traverse up.

2. Can you store O(n) additional data? You could traverse it in a normal breadth-first manner, inserting pointers into a priority queue by level, as with the previous solution, but this time inserting all nodes during the initial traversal. This will increase the maximum size of the auxiliary data used during traversal though.

3. Is the tree guaranteed to be balanced and full, like it might be in a Heap-like tree? If it is, you can traverse it in a simpler manner, by just going to the right places.

Answer 4

I explain in a better way. I have an algebraic expression tree (so not balanced). I have to valuate it USING a queue (and only a queue). I asked this question because I think the only way is to take nodes starting from the lowest level, till the root...

example: tree ( + ( * ( 2 ) ( 2 ) ) ( 3 ) )

I take the queue and:

enqueue(1); enqueue(2);

(*) -----> dequeue; dequeue; result = 2 * 2; enqueue(result); enqueue 3; (+) -----> dequeue; dequeue; result = 4 + 3; give result;

so I need to have this traversal: 2 ; 2 ; * ; 3 ; +

I dont know if it's clear...

Answer 5

Queue is only useful for traversing level-order from root to leaf of the tree.

You can use a Depth-first Traversal for printing a certain level. Like this:

 void printLevel(BinaryTree *p, int level) {
   if (!p) return;
   if (level == 1) {
     cout << p->data << " ";
   } else {
     printLevel(p->left, level-1);
     printLevel(p->right, level-1);
   }
 }

To print all levels from leaf up to root, you would need to find the maximum depth of the tree. This could be done easily using depth-first traversal as well (You can easily google the solution).

void printLevelOrder(BinaryTree *root) {
  int height = maxHeight(root);
  for (int level = height; level >= 1; level--) {
    printLevel(root, level);
    cout << endl;
  }
}

The run time complexity is surprisingly, O(N), where N is the total number of nodes.

For more information and run-time complexity analysis, refer to the page below:

http://www.ihas1337code.com/2010/09/binary-tree-level-order-traversal-using_17.html