0% completed
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 of3
in this order is4
.
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 of9
in this order is10
.
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 of12
in this order is7
.
Constraints:
- The number of nodes in the tree is in the range [0, 10<sup>5</sup>].
-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
-
Initialize a Queue:
- If the tree is empty (
root == null
), returnnull
immediately. - Create a queue and enqueue the
root
node.
- If the tree is empty (
-
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.
- If the value of the dequeued node equals
- While the queue is not empty:
-
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
-
Initialize BFS:
- Start with the root node
12
. - Initialize a queue and enqueue
12
.
Queue:
[12]
- Start with the root node
-
Process Level 1 (Root Node):
- Dequeue
12
, process it. - Enqueue left child
7
. - Enqueue right child
1
.
Queue:
[7, 1]
- Dequeue
-
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]
- Dequeue
-
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]
- Dequeue
-
Return the Next Node:
- The front of the queue is
10
, which is the level order successor of9
.
- The front of the queue is
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
The time complexity of the above algorithm is O(N), 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 O(N) 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 O(N) space to store them in the queue.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible