Deepest node in a binary tree

Abhishek Kumar Category: Data StructuresTags: datastructures tree binary-tree

The rightmost node among the leaf nodes is known as the deepest node in a binary tree.
Find the deepest node in a binary tree solution with examples and algorithm.

Deepest node in a tree

Deepest node in a tree

The rightmost node among the leaf nodes is known as the deepest node in tree.

Deepest node in a tree example

To find the deepest node in a binary tree we can traverse through all the the nodes in a tree and return the rightmost node among the leaf nodes.

Example -
Input: 
      1
    /   \
   2     3
  / \   / \
 4   5 6   7
      /
     8
      \
       9

Output: 9

Solution

For the solution, we have to traverse each node and this can be achieved by using level order traversal and at the end return the deepest node.

Algorithm
Deepest_Node(root)
1.  if root is null then return null
2.  node = null
3.  queue.enqueue(root)
4.  while queue is not empty
5.      queue.dequeue()
6.      if node.left is not null
7.          queue.enqueue
8.      if node.right is not null
9.          queue.enqueue
10. return node.data
import queue

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def deepest_node(root):
    if root is None:
        return None
    
    node = None
    q = queue.Queue()
    q.put(root)

    while not q.empty():
        node = q.get()
        if node.left:
            q.put(node.left)
        if node.right:
            q.put(node.right)
    return node.data

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(deepest_node(root))
class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function deepestNode(root) {
  if (!root) return null;

  let node = null;
  q = [];
  q.push(root);

  while (q.length > 0) {
    node = q.shift();
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return node.data;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
console.log(deepestNode(root));

Output

Output

7

Time complexity: The time complexity of this solution is O(n) because we are just traversing each element of node one by one.


AUTHOR

abhishek

Abhishek Kumar

Software engineer | Blogger | Keen learner
Python | Django | JavaScript | React | Next.js | Express.js | C
Passionate about learning and experimenting with new things and open to more opportunities and collaborations.