Find the depth of a tree without using recursion

In my last post, I discussed how to find  the depth of a tree using recursion. Now I’ll point out the way of doing this without using recursion. I hope everyone knows what a Breadth-First Search (BFS) is. To explain it in short, you add all the child nodes of root in a queue. Then you pop a node out of the front and add the child nodes of that to the end of the queue. In this way, you traverse a tree in a  Breadth-First manner.

Similarly, all you need to do is add a random value “X” to the queue once you have added the children of root. Now start popping and proceed with BFS. When you encounter the “X”, you add another “X” at the end of the queue and increase the value of depth (initially 0). In essence, every “X” occurs after you have added the nodes at one level. So your depth variable ends up having the number of “X”es or depth of the tree at the end of your program when your queue is empty. 🙂

Here is the algorithm (in words) to make things clearer,

1. Add ROOT to queue

2. Pop ROOT, Add its child nodes to queue, Add “X” to queue

3. Pop elements from queue. (If not “X”, add its child nodes to the queue, else, add “X” to the queue and increment depth)

4. Go to Step 3 till queue is NOT empty.

You have it! The depth of your tree in time complexity O(V+E). This method is useful when you don’t have a lot of memory to use and can’t afford to load the memory stack through recursion.

See you soon!