Binary Tree Right Side View - Java Solution

1. Introduction

This blog post focuses on a unique perspective of binary trees - the right side view. In this problem, we aim to visualize a binary tree from the right side and determine which nodes are visible when viewed from this angle. This task is a variation of tree traversal that combines elements of depth-first and breadth-first searches.

Problem

Given the root of a binary tree, the objective is to return the values of the nodes as seen from the right side of the tree, ordered from top to bottom.

2. Solution Steps

1. Perform a level-order traversal (breadth-first search) of the tree using a queue.

2. For each level, record the value of the last node in that level.

3. Traverse each level of the tree and add the last node of each level to the result list.

4. Return the list of node values that represent the right side view of the tree.

3. Code Program

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

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

public class BinaryTreeRightSideView {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);

        System.out.println(rightSideView(root)); // Test the function
    }

    // Function to get the right side view of a binary tree
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if (i == levelSize - 1) {
                    // Add the last node of each level to the result
                    result.add(currentNode.val);
                }
                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer(currentNode.right);
            }
        }

        return result;
    }
}

Output:

[1, 3, 4]

Explanation:

1. rightSideView: This function implements a level-order traversal of the binary tree using a queue.

2. For each level, it iterates through all nodes at that level. The last node in each level (rightmost node) is added to the result list.

3. If a node has left or right children, they are added to the queue for subsequent processing.

4. The function continues this process until all levels are traversed.

5. The result list represents the right side view of the tree, showing the last (rightmost) node at each level when viewed from the right side.