Home > Applied Algorithms, Iteration, Tree > Find the depth of a tree without using recursion

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!

About these ads
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 260 other followers

%d bloggers like this: