CodingGyan

Binary Tree Right Side View

medium Data Structures and Algorithms

Problem

The tree is given in level order on one line, with null for a missing child. Imagine that you stand on the right side of the tree and look at it. Print the values of the nodes that you can see, from the top to the bottom, separated by single spaces. (On each level you see the right-most node.)

Constraints

  • 0 <= n <= 10^4 nodes

Examples

Input

1 2 3 null 5 null 4

Output

1 3 4

Solutions

Best approachTime O(n)Space O(w)

A breadth-first walk visits one level after the other. The last node of a level is the right-most one, so it is the node that you see from the right side.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a binary tree.
 * Input   : One line: the tree in level order.
 * Output  : The right side view.
 * Approach: Level by level.
 * Time    : O(n)
 * Space   : O(w)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
        // Step 1: A tree node has a value and links to the left and right child. null means: no child.
        static class TreeNode {
            int value;
            TreeNode left;
            TreeNode right;

            TreeNode(int value) {
                this.value = value;
            }
        }

        // This method builds a tree from the level order tokens. A queue keeps the nodes that still need children.
        static TreeNode build(String[] tokens) {
            if (tokens.length == 0 || tokens[0].equals("null")) {
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
            java.util.ArrayDeque<TreeNode> queue = new java.util.ArrayDeque<>();
            queue.add(root);
            int i = 1;
            while (!queue.isEmpty() && i < tokens.length) {
                TreeNode node = queue.poll();
                if (i < tokens.length && !tokens[i].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.add(node.left);
                }
                i++;
                if (i < tokens.length && !tokens[i].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.add(node.right);
                }
                i++;
            }
            return root;
        }

    // This method solves the task. It receives the input and returns the answer.
    static int[] solve(String s) {
        // Step 3: Go level by level. The last node of each level is the one that is seen from the right.
        TreeNode root = build(s.trim().split(" "));
        java.util.List<Integer> seen = new java.util.ArrayList<Integer>();
        java.util.ArrayDeque<TreeNode> queue = new java.util.ArrayDeque<TreeNode>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    seen.add(node.value);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        int[] out = new int[seen.size()];
        for (int i = 0; i < out.length; i++) {
            out[i] = seen.get(i);
        }
        return out;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(Arrays.stream(solve(s)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Hints (1)
  1. Which node of a level can you see?

Try these next