Finding deepest node of a binary tree.

Question

We want to find an algorithm for finding the deepest node of a binary tree.

My idea is to use BFS (Breadth-first search) and while visiting each node we will initialize it's node.dvalue(which will indicate how much far is node away from the source(root)).

When my algorithm will terminate, I will find that node for whose dvalue is maximum, and that will give me node with the highest depth.

Is my above-suggested algorithm correct?

Comments

Yes your logic is right.

We can do this in O(n) time using BFS.

---

why r u using BFS instead of DFS?

Deepest means more depth

rt?

---

BFS would be more suitable because it will give me the node which is far away from the root(the deepest node).

BFS would tell me how far a node is from the root.

and the farthest node will be the deepest node.

---

think both will work

https://cs.stackexchange.com/questions/22855/algorithm-to-find-diameter-of-a-tree-using-bfs-dfs-why-does-it-workI 

Answer 1

As per my thinking we should go for DFS as we don't want to know about every intermediate node. We want to find the farthest node from root which will yeild the highest hight.

BFS will also be correct.