Ask: How to find the rightmost node of the last layer of a complete binary tree

aresyt

As the title.
It is easy to implement a complete binary tree based on array, just return the last item of the array.
But what algorithm should be used for a full binary tree based on pointer implementation?
Thank you very much!

xiaobaixi

Right subtree of right subtree

Until the last layer

Isn't it OK?

aresyt

No, a complete binary tree is not necessarily a full binary tree.
In the last layer, all nodes are arranged seamlessly from left to right.

冷夜星光

Indeed, finding it with GoFastRight (); is a bit cumbersome!

mars1004

Breadth-first search.

zphoenix

:) Use a linked list to do a hierarchical search.
On the first level, throw the root into the linked list.
In the second layer, find the L and R children of the root and replace the root in the linked list.
In the third layer, find the child nodes of the root L and R child nodes and replace them in the linked list.
In this recursion, if a node has no children, it is deleted, otherwise it is replaced by its own children. Keep child nodes in order from left to right.
This way to the last level, the last child node is what you are looking for.

Of course, when it is implemented, it is necessary to traverse one layer before deleting the previous one. :)

aresyt

Oh I see.
That is to say, the queue-based breadth-first traversal is used. Each time a visited node is popped from the queue into the stack, the data item on the top of the stack after the traversal is requested.
The complexity of this algorithm is indeed much greater than that of array-based ones.

菜鸟级高手

Last node traversed by layer

ch1074856

Keep looking for the right sub-tree from the beginning. If there is no right sub-tree, look for the left sub-tree. All the way to the leaf node.

ch1074856

The abovech1074856method is wrong, please ignore it.