Given a binary tree, write a method to find and return its deepest node. Return null for an empty tree.

Example: 1 / \ 2 3 ==> deepest = 9 / \ / \ 4 5 6 7 / \ 8 9

Need a **hand?** Try out these hints, one at a time.

Traverse the tree level by level. The last node at the last level of the tree is the deepest node

`Queues`

are helpful for level by level traversal of binary trees.Queue all the nodes at a level, dequeue a node and enqueue its left and right nodes.

1. Create a

2. Enqueue the

Repeat step 3 and 4 below

3. In a

4.

5. The last node to come out of the

`Queue`

of tree nodes `Queue<TreeNode> q`

.2. Enqueue the

`root`

and follow steps 3 - 4 below : Repeat step 3 and 4 below

3. In a

`while`

loop traverse the tree, and store all the nodes of each level in the queue.4.

`Deque`

nodes and enqueue their child nodes.5. The last node to come out of the

`Queue`

is the deepest node.
public TreeNode findDeepest(TreeNode root) { }

**C**

**Java**

**Python**