Deepest Node in a Given Tree algorithem

[darje]

i have some algorithem i saw in some book
how to find the deepest node in a tree
i didnt quite understand how its work
can someone illustriate it to me how the program run

 find(Binarytree* root)){
queue *q;
if(!root) return null;
q=createqueue();
enquue(q,root) //<- here i put all the element in tree in queue right?
while(!isemptyqueue){
temp=dequeue(q)
if(temp->left)
enqueue(q,temp->right)
if(temp->right)
enqueue(q,temp->right)

the code isnt important i just want to understand how its work
didnt quite understand that
just want someone to poing me how its work.

[dhayden]

I think enquue() enqueues a single node pointer and dequeue() dequeues it. The queue contains nodes that you need to process. Line 5 enqueues the root node. The loop starting at line 6 dequeues one node and enqueues the children.

The result is that every node will be visited in breadth first order. So, for example, if you print out the address or value of the node temp after line 7, you'll see that it prints them in breadth first order.

There is no code here to find the deepest node.

[jonnin]

its hard to say what line 5 does. Normal queues add 1 item at a time, but this could indeed be a bulk insert of the whole tree, as its apparently something the author hand-rolled (note the oddly spelled enqueue)

I am going to guess that you are wrong as the subsequent code adds more items to the queue via the enqueue statements, but notice here, a different spelling. Its NOT the same function. But I have no idea what is different between them, or maybe its a typo and the code won't compile.

As for finding the deepest node, this seems convoluted.
a tree traversal that simply tracks the depth and holds onto the deepest found as each element is examined is a more straightforward way to do it (all this queue stuff feels inefficient, as all you really need is to touch each item). As a side note, this is the sort of thing that if you need it, its better to track it as you go than to go looking for it later. Every time you insert an item into your tree class, just check it and update a current deepest node variable. Then when you need it, you have it.

The code you posted is too badly broken to try to explain. Not only the 2 spellings of NQ but it adds to right whether the item was left OR right, which can't possibly be correct. Throw this away and find something that works to study!

[darje]

the code is broken idd
as i said the code is not important i try to understand it beyond the code.

[Duthomhas]

It is difficult to understand only several pieces of a thing. Look at the whole solution or understand that your comprehension will not be complete.

There are two basic methods for traversing any n-ary tree:

 • depth-first search (DFS)
 • breadth-first search (BFS)

Both have value. Both are worth googling. The snippet you posted above is a BFS. The deepest node will be reported as the last node processed.

Keep in mind that there may be more than one “deepest” node; without some additional help/modification BFS will not tell you this. IMO, modifying it to get all deepest nodes is more work with BFS than it is worth.

I would personally use a DFS and keep a list of deepest nodes yet encountered, much like you find the smallest/largest value(s) in an array. At completion your list will be all the deepest nodes. IMO this is the simplest solution.

In order to gain understanding, google BFS and DFS and watch the videos/animated HTML/etc and write yourself a simple algorithm to do it. (You can easily create everything in C++ in 50 lines or fewer.)

Good luck!