Hello everyone. In this lecture of Data Structure and Algorithm, we’re going to learn
the algorithms related to breadth-first search of the ADT of binary tree.
That is, we access every nodes from the top to the bottom, and
from the left to the right.
We can see from it, there is an FIFO property in this process. Thus,
we can use a queue to store the information of nodes we’re going to access
For such a binary tree, we first
push the root node to the queue, and we pop a node from
the head of the queue. We access the node when we pop it, and the node to the sequence of BFS.
Then we push its left and right children which are not null to
the queue. After we access this node, we
find a new element from the head and repeat the
process, then we get a sequence of BFS.
Let’s see the algorithm of this BFS.
First, we make the pointer point to
the root. If the root is not null, we push it to
such a queue. Then,
if the queue is not null, we
get the element from the head of the queue,
and access the data information of the element.
Then we push the left and right children which are not null
of this element, i.e. the current pointer, to
the tail of the queue, and continue to pop an
element from the head of the queue, until the queue is empty. Every node has
been processed. In the traversal algorithm of binary tree,
every node is accessed once,
so the time complexity is O(n), in the
BFS, we use a queue to help us.
Every node is pushed and popped once, so the time complexity is O(n).
As for the space complexity, it is related to the
maximum breadth of the tree. In beast case, the tree is linear,
so every node is pushed and popped
once, this is the best case for the space complexity but of course
not a good case for time complexity, because we want the tree is as short as possible,
that is the height is as close to log n as possible. So a lot of operations can be
O(log n). The worst case of the time complexity is in fact the
the best case of the organizational structure of the binary tree.
In this case, the height is order of log n and is close to that of complete binary tree.
So the contents in the queue at some time may be
O(n), this is the worst case of space complexity. At that time,
the time complexity is low.
At last, think about some questions.
What is similarity between BFS traversal and
non-recursive pre-order traversal? Thank you all!