Alternatively, we can check index when iterating a level, and only add i == n-1 to the result. This does not require changing appending order for children, which is usually [left, right].
for i in range(n): # iterate all i for a level
node = queue.popleft()
if i == n - 1: # only take last i (rightmost)
result.append(node.val)
We can use the fact that indexing into a list is O(1) time and avoid changing the logic much. Below I just look at the end of the queue at each level to get the rightmost node. Traverse the same way as the previous problems.
def binary_tree_right_side_view(root: Node) → List[int]:
output = []
if root is not None:
queue = deque([root])
while queue: #[ ]
n = len(queue) # 1
rightmost_node = queue[-1]
output.append(rightmost_node.val) #[1,3,6,7]
for _ in range(n): # 0
curr = queue.popleft() # 7
for child in [curr.left,curr.right]: # n,n
if child is not None:
queue.append(child)
return output
Is it bad that I can’t think of the solution myself, but once I read the solution code I get it instantly?
It’s totally normal.
c# using LinkedList as FIFO Deque
public static List<int> BinaryTreeRightSideView(Node<int> root)
{
var res = new List<int>();
if (root == null) return res;
var queue = new LinkedList<Node<int>>();
queue.AddFirst(root); // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{ // as long as there is element in the queue
int n = queue.Count; // number of nodes in current level
res.Add(queue.Last.Value.val); // only append the first node we encounter since it's the rightmost
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Last.Value;
queue.RemoveLast();
// we add right children first so it'll pop out of the queue first
if (node.right != null) queue.AddFirst(node.right);
if (node.left != null) queue.AddFirst(node.left);
}
}
return res;
}
c# using Queue, wasnt familiar with Queue yet in c# so used LinkedList Before.
public static List<int> BinaryTreeRightSideView(Node<int> root)
{
var res = new List<int>();
if (root == null) return res;
var queue = new Queue<Node<int>>();
queue.Enqueue(root); // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{ // as long as there is element in the queue
int n = queue.Count; // number of nodes in current level
res.Add(queue.Peek().val); // only append the first node we encounter since it's the rightmost
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Dequeue();
// we add right children first so it'll pop out of the queue first
if (node.right != null) queue.Enqueue(node.right);
if (node.left != null) queue.Enqueue(node.left);
}
}
return res;
}
I think the real reason is ‘we are ordinary’.
for any Go people
type NodeQueue []Node
func (q *NodeQueue) Enqueue(n Node) {
*q = append(*q, n)
}
func (q *NodeQueue) Dequeue() Node {
el := (*q)[0]
*q = (*q)[1:]
return el
}
func binaryTreeRightSideView(root *Node) []int {
result := []int{}
if root == nil {
return result
}
var q NodeQueue
q.Enqueue(*root)
for len(q) > 0 {
size := len(q)
level := []int{}
for i := 0; i < size; i++ {
current := q.Dequeue()
level = append(level, current.val)
if current.left != nil {
q.Enqueue(*current.left)
}
if current.right != nil {
q.Enqueue(*current.right)
}
}
result = append(result, level[len(level)-1])
}
return result
}
func main() {
root := Node{1, nil, nil}
root.left = &Node{2, nil, nil}
root.right = &Node{3, nil, nil}
root.left.left = &Node{4, nil, nil}
root.left.right = &Node{5, nil, nil}
root.right.right = &Node{6, nil, nil}
root.left.left.right = &Node{7, nil, nil}
root.left.right.right = &Node{8, nil, nil}
fmt.Println(zigZagTraversal(&root))
}
NOTE - in main it should be calling binaryTreeRightSideView not zigZagTraversal - thats a typo
To continue on with the previous patterns in the previous questions. We can also just use a variable to keep track of the last Node. Whichever is the last seen in the loop when traversing through the nodes in the current level, is the right most node. See below in Java.
public static List binaryTreeRightSideView(Node root) {
if (root == null) {
return List.of();
}
List<Integer> result = new ArrayList<>();
// Initialize bfs
var queue = new ArrayDeque<Node<Integer>>();
queue.add(root);
// Continue while queue is not empty
while (!queue.isEmpty()) {
// Keep track of current number of nodes in level
int n = queue.size();
// Use variable to keep track of last node that is removed in loop
Integer lastNode = null;
// Go through all nodes in level
for (int i = 0; i < n; i++) {
// Get node in end
var current = queue.remove();
// Update last Node
lastNode = current.val;
// Add all children
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
// Add last node that was seen in the loop
result.add(lastNode);
}
return result;
}
you are welcome
public static List<Integer> binaryTreeRightSideView(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
Queue<Node<Integer>> q = new LinkedList();
List<Integer> result = new ArrayList();
q.add(root);
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
Node<Integer> n = q.remove();
if(n == null) continue;
if( i == size - 1)
{
result.add(n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
}
return result;
}
There is a typo in line 14 of the JavaScript solution. It currently says:
res.push(queue[0].val); // only append the first node we encounter since it's the rightmost
However, we should be getting queue[queue.length - 1] instead.
def binary_tree_right_side_view(root: Node) -> List[int]:
if not root:
return []
res = []
queue = deque([root])
while queue:
res.append(queue[-1].val)
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
dfs solution
def binary_tree_right_side_view(root: Node) -> List[int]:
rst = []
def dfs(node, level=0):
if not node:
return
if level >= len(rst):
rst.append(node.val)
dfs(node.right, level + 1)
dfs(node.left, level + 1)
dfs(root)
return rst