Tip:
Highlight text to annotate it
X
In this lesson, we are going to write code for level order traversal of a binary tree.
As we had discussed in our previous lesson, in level order traversal, we visit all nodes
at a particular depth or level before visiting the nodes at next deeper level. For this binary
tree that I am showing here, if I have to traverse the tree and print the data in nodes
in level order, then this is how we will go. We will start at level 0 and print F and now
we are done with level-0, so we can go to level 1 and we can visit the nodes at level
1 from left to right. From F we will go to D and from D we will go to J. Now level 1
is done, so we can go to level 2. So, we will go like B, E, G and then K and now we can
go to next level. A, C, I and finally we will be done at H. his is the order in which we
should visit the nodes, but the question is, how can we visit the nodes in this order in
a program. Like linked list, we can't just have one pointer and keep moving it. If I'll
start with a pointer at root, lets say I have a pointer named current to point to the current
node that I am visiting, then its possible for me to go from F to D using this pointer
because there is a link. So, I can go left to D. But from D, I cannot go to J because
there is no link from D to J. The only way we can go to J is from F and once we have
moved the pointer to D, we can't even go back to F because there is no backward link from
D to F. So, what can we do to traverse the nodes in level order. Clearly, we cant go
with just one pointer. What we can do is, as we visit a node, we can reference or address
of all its children in a queue, so we can visit them later. A node in the queue can
be called discovered node whose address is known to us, but we have not visited it yet.
Initially, we can start with address of root node in the queue to mean that initially this
is the only discovered node. Lets say for this example tree, address of the root node
is 400. And I'll assume some random addresses for other nodes as well. I will mark a discovered
node in yellow. Ok, now initially I am enqueuing the root node and by storing a node in the
queue, I'll mean storing the address of the node in the queue. So, initially, we are starting
with one discovered node. Now as long as the queue has some discovered node, at least one
discovered node i.e as long as the queue is not empty, we can take out a node from the
front, visit it and then enqueue its children. Visiting a node for us is printing the value
in that node, so I'll write F here. And now, I'll enqueue the children of this root node.
First I'll enqueue the left child and then the right child. I'll mark visited node in
another color. Ok, now we have one visited node and 2 discovered nodes. And now once
again, we can take out the node at front of the queue, visit it and enqueue its children.
By using a queue, we are doing 2 things here. First of all, as we are moving from a node,
we are not loosing reference to its children because we are storing the references and
then because queue is a first in first out structure, so a node that is discovered first,
that is inserted first will be visited first. So, we will get this order that we are desiring.
Give this some thought and its not very difficult to see. Ok, so now we can dequeue and visit
this node at address 200. And once again, before I move on from this node, I need to
enqueue its children. So, now at this stage we have 2 visited nodes, 3 discovered nodes
and 6 undiscovered nodes. And now we can take out the next node from front of queue. We'll
visit it and enqueue its children. If we will go on like this, all the nodes will be visited
in the order that we are desiring. At this stage, we can dequeue node at 120, visit it
and enqueue its children. So, we will go on like this until all the nodes are visited
and the queue is empty. After B, we will have E here. Nothing will go into the queue this
time. Next we will have G here and the address of I will go into the queue. Now, K will be
visited. Now at this stage, we have reference to 3 Nodes in the queue. Now, we will visit
this node at 320 with value A. Then we have C and now we will print I and the node with
value H, the node with data H will go into the queue. Finally, we will visit this node
and now we are done with all the nodes, the queue is empty. Once the queue is empty, we
are done with our traversal. So, this is the algorithm for level order traversal of a binary
tree. As you saw, in this approach, at any time, we are keeping a bunch of addressees
in the memory, in the queue instead of using just one pointer to move around. So, of course
we are using a lot of extra memory and I'll talk about the space complexity of this algorithm
in some time. I hope you got the core logic right. Lets now write code for this algorithm.
I am going to write C++ here. This is how I am defining node for my binary tree. I have
a structure here with 3 fields, one to store data and the data-type is character this time,
because in the example tree that we were showing earlier, data type was character and we have
2 more fields that are pointers to node - one to store the address of left child and another
to store the address of right child. Now, what I want to do here is I want to write
a function named LevelOrder that should take address of the root node as argument and print
the data in the nodes in level order. Now, to test this function, I'll have to write
a lot of code to create and insert nodes in a binary tree. I'll have to write some more
functions. I'll skip writing all that code. You can pick the code for creation and insertion
from previous lessons. All I'll write is this function LevelOrder. Now, in this function
here, I'll first take care of one corner case. If the tree is empty i.e if root is NULL,
we can simply return, else if the tree is not empty, we need to create a queue. I'm
not going to write my own implementation of queue here. In C++, we can use the queue in
standard template library and to use it, first we will have to write a statement like #include
here. And now, I can create a queue of any type. In this function, I'll create a queue
of pointer to node with a statement like this. Now, as we had discussed earlier, initially,
we start with one discovered node in the queue. The only node known to us initially is the
root node. With this statement, queue.push(root), I have inserted the address of root node in
the queue. And now, I will run this while loop for which the condition is that queue
should not be empty and what I really mean here is that while there is at least one discovered
node, we should go inside the loop and inside the loop, we should take out a node from the
front. This function front returns the element at front of the queue and because the data-type
is pointer to node, I'm collecting the return of this function in this pointer to node named
current. Now, I can visit this node being pointed by current and by visiting, we mean
reading the data in that node. I'll simple print the data. And now, we want to push the
addresses of children of this node into the queue. So, I'll say that if the left child
is not NULL, insert it into the queue and similarly, if right child is not NULL, push
it into the queue or rather push its address into the queue. And I'll write one more statement
to remove the element from front of the queue. With call to front, the element is not removed
from the queue. With this call pop, we are removing the element. Ok, so this is implementation
of level order traversal in C++. You can check the description of this video for link to
source code and there you can also find all the extra code to test this function. Lets
now talk about time and space complexity of level order traversal. If there are n Nodes
in the tree and in this algorithm, visit to a node is reading the data in that node and
inserting its children in the queue, then a visit to a node will take constant time
and each node will be visited exactly once. So, time taken will be proportional to the
number of nodes. Or in other words, we can say that the time complexity is big-oh of
n. For all cases, irrespective of the shape of the tree, time complexity of level order
traversal will be big-oh of n. Now lets talk about space complexity. Space complexity,
as we know is the measure of rate of growth of extra memory used with input size. We are
not using constant amount of extra memory in this algorithm. We have this queue that
will grow and shrink while executing this algorithm. Assuming that the queue is dynamic,
maximum amount of extra memory used will depend upon maximum number of elements in the queue
at any time. We can have couple of cases. In some cases, extra memory used will be lesser
and in some cases, extra memory used will be greater. For a tree like this where each
node has only one child, we will have maximum one element in the queue at any time. During
each visit, one node will be taken out from the queue and one node will be inserted. So,
the amount of extra memory taken will not depend upon the number of nodes. Space complexity
will be big-oh of 1. But for a tree like this, the amount of extra memory used will depend
upon number of nodes in the tree. This is a perfect binary tree. All the levels are
full. If you can see, as the algorithm will execute, at some point for each level, all
the nodes in that level will be in the queue. In a perfect binary tree, we will have n/2
nodes at the deepest level. So, maximum number of nodes in the queue is going to be at least
n/2. So, basically extra memory used is proportional to n - the number of nodes. So, space complexity
will be big-oh of n for this case. I'm not going to prove it, but for average case, space
complexity will be O(n). So, for both worst and average cases, we will be big-oh of n
in terms of space complexity and when we are saying best, average and worst cases here,
its only going by space complexity. Time complexity will be big-oh of n for all cases. So, this
is time and space complexity analysis of level order traversal. I'll stop here now. In next
lesson, we will discuss depth first traversal algorithms - Preorder, Inorder and PostOrder.
This is it for this lesson. Thanks for watching !