easy Level Order Successor

Problem Statement

Given a root of the binary tree and an integer key, find the level order successor of the node containing the given key as a value in the tree.

The level order successor is the node that appears right after the given node in the level order traversal.

Examples

Example 1

• Input: root = [1, 2, 3, 4, 5], key = 3

• Output: 4
• Explanation: The level-order traversal of the tree is [1, 2, 3, 4, 5]. The successor of 3 in this order is 4.

Example 2

• Input: root = [12, 7, 1, 9, null, 10, 5], key = 9

• Output: 10
• Explanation: The level-order traversal of the tree is [12, 7, 1, 9, 10, 5]. The successor of 9 in this order is 10.

Example 3

• Input: root = [12, 7, 1, 9, null, 10, 5], key = 12

• Output: 7
• Explanation: The level-order traversal of the tree is [12, 7, 1, 9, 10]. The successor of 12 in this order is 7.

Constraints:

• The number of nodes in the tree is in the range [0, 10⁵].
• -1000 <= Node.val <= 1000

Solution

To solve this problem, we use Breadth-First Search (BFS) to traverse the tree level by level and find the level order successor of a given node. We maintain a queue to keep track of nodes at each level. Starting from the root, we enqueue each node's children and process nodes sequentially. As we dequeue nodes, we check if the current node matches the key value. Once we find the key node, the next node in the queue (if any) is its level order successor.

Step-by-Step Algorithm

1. Initialize a Queue:

   • If the tree is empty (root == null), return null immediately.
   • Create a queue and enqueue the root node.

2. Perform Level Order Traversal Using BFS:

   • While the queue is not empty:
     • Dequeue the front node.
     • Enqueue its children:
       • If the left child exists, enqueue it.
       • If the right child exists, enqueue it.
     • Check if the current node matches the target (key):
       • If the value of the dequeued node equals key, break out of the loop to stop the BFS traversal.

3. Return the Next Node in the Queue:

   • The front of the queue now holds the level order successor.
   • If the queue is empty, return null (meaning no successor exists).

Algorithm Walkthrough

1. Initialize BFS:

   • Start with the root node 12.
   • Initialize a queue and enqueue 12.

   Queue: [12]

2. Process Level 1 (Root Node):

   • Dequeue 12, process it.
   • Enqueue left child 7.
   • Enqueue right child 1.

   Queue: [7, 1]

3. Process Level 2:

   • Dequeue 7, process it.
   • Enqueue left child 9 (No right child).

   Queue: [1, 9]

   • Dequeue 1, process it.
   • Enqueue left child 10.
   • Enqueue right child 5.

   Queue: [9, 10, 5]

4. Process Level 3 (Finding Target Node):

   • Dequeue 9, process it.
   • Target found (9), so we break out of the loop.

   Queue after breaking: [10, 5]

5. Return the Next Node:

   • The front of the queue is 10, which is the level order successor of 9.

Code

Here is the code for this algorithm:

import java.util.*;

// class TreeNode {
//   int val;
//   TreeNode left;
//   TreeNode right;

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {
  public TreeNode findSuccessor(TreeNode root, int key) {
    if (root == null)
      return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      TreeNode currentNode = queue.poll();
      // insert the children of current node in the queue
      if (currentNode.left != null)
        queue.offer(currentNode.left);
      if (currentNode.right != null)
        queue.offer(currentNode.right);

      // break if we have found the key
      if (currentNode.val == key)
        break;
    }

    return queue.peek();
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    
    TreeNode result = sol.findSuccessor(root, 3);
    if (result != null)
      System.out.println(result.val + " ");

    root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(9);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);

    result = sol.findSuccessor(root, 9);
    if (result != null)
      System.out.println(result.val + " ");

    result = sol.findSuccessor(root, 12);
    if (result != null)
      System.out.println(result.val + " ");
  }
}

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be which is required for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.