700308. Extreme nodes in alternate order
Extreme nodes in alternate order
Slug: extreme-nodes-in-alternate-order Difficulty: Medium Id: 700308 Topic Tags: Tree, Data Structures Company Tags: Amazon
Summary
Given a binary tree, find the nodes that are at an odd distance from the root node. In other words, if we start traversing the tree from the root and visit each node in alternate order (i.e., skip one node and then visit the next), the nodes that will be visited will be the extreme nodes. This problem requires understanding of binary trees and traversal algorithms.
Detailed Explanation
The given problem can be solved by using a level-order traversal algorithm with some modifications to keep track of the nodes at odd distances from the root. We'll use a queue to perform the level-order traversal and an integer variable, level, to keep track of the current level.
Here's a step-by-step breakdown of the solution:
- Initialize an empty queue and add the root node to it.
- Initialize an empty list to store the extreme nodes.
- Perform level-order traversal using the queue:
- Dequeue a node from the front of the queue.
- If the dequeued node is at an odd distance from the root (i.e.,
levelis odd), add it to the list of extreme nodes. - Add all the child nodes of the dequeued node to the back of the queue. Increment
levelby 1 for each child node.
- Return the list of extreme nodes.
Time complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the level-order traversal. Space complexity: O(N), as we need to store all the nodes at a given level in the queue, which can grow up to N for a skewed tree.
Optimized Solutions
Java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<TreeNode> extremeNodes(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (level % 2 != 0) { // nodes at odd distances
result.add(node);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
level++;
}
return result;
}
}