The Right View of binary tree refers to the set of nodes visible when the tree is viewed from the right side. In other words, for each level (or depth) of the tree, only the rightmost node at that level is included in the view.

To implement the Right View of a binary tree algorithmically, we can utilize a level-order traversal (Breadth-First Search) with a queue to capture the rightmost nodes of each level

Code Flow for Print Right View of Binary Tree

• Start Right View Traversal:

  • Check if root is null.

    • If true: Return.

    • If false: Initialize a queue with root.

• Level Order Traversal:

  • For each level:

    • Count the number of nodes (size) in the level.

    • Process each node:

      • If it’s the last node of the level (i == size - 1), add to the right view.

      • Add the left and right children of the current node to the queue.

• Output Right View:

  • Print the data of the rightmost nodes for each level.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

@Data
class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinarySearchTree {
    Node root;

    public static void rightView(Node root) {
        /*  If root is null, return */
        if (Objects.isNull(root)) {
            System.out.println("the root is null");
            return;
        }
        /*  Performs a level-order traversal using a queue.   */
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        /*  Iterates through the tree level by level   */
        while (!queue.isEmpty()) {
            int size = queue.size();
            /*  Tracks the size of the queue to process nodes level-wise.   */
            for (int i = 0; i < size; i++) {
                Node curr = queue.peek();
                queue.remove();
                if (i == size - 1) {
                    System.out.print("[" + curr.data + "]");
                }
                /*  Adds the left children of the current node to the queue.  */
                if (Objects.nonNull(curr.left)) {
                    queue.add(curr.left);
                }
                /*  Adds the right children of the current node to the queue.  */
                if (Objects.nonNull(curr.right)) {
                    queue.add(curr.right);
                }
            }
        }
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertDoesNotThrow;

public class BinarySearchTreeTest {

    @Test
    void testNullRoot() {
        // Test edge case: Null root (tree is empty)
        Node root = null;
        assertDoesNotThrow(() -> BinarySearchTree.rightView(root));
        // Expect no output
    }

    @Test
    void testSingleNodeTree() {
        // Test edge case: Tree with a single node
        Node root = new Node(1);
        BinarySearchTree.rightView(root);
        // Expect output: "1"
    }

    @Test
    void testCompleteBinaryTree() {
        // Test case: Complete binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        BinarySearchTree.rightView(root);
        // Expect output: "1 3 7"
    }

    @Test
    void testLeftSkewedTree() {
        // Test edge case: Left-skewed tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(3);
        BinarySearchTree.rightView(root);
        // Expect output: "1 2 3"
    }

    @Test
    void testRightSkewedTree() {
        // Test edge case: Right-skewed tree
        Node root = new Node(1);
        root.right = new Node(2);
        root.right.right = new Node(3);
        BinarySearchTree.rightView(root);
        // Expect output: "1 2 3"
    }

    @Test
    void testUnevenTree() {
        // Test case: Uneven tree structure
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.right = new Node(4);
        root.right = new Node(3);
        root.right.left = new Node(5);
        BinarySearchTree.rightView(root);
        // Expect output: "1 3 5"
    }

    @Test
    void testRightViewComplexTree() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(10);
        binarySearchTree.insert(5);
        binarySearchTree.insert(15);
        binarySearchTree.insert(3);
        binarySearchTree.insert(7);
        binarySearchTree.insert(12);
        binarySearchTree.insert(18);
        binarySearchTree.insert(1);
        BinarySearchTree.rightView(binarySearchTree.root);
        // Expect output: "10 15 `8 1"
    }

    /*  Binary Search Tree is every node's right subtree contains values greater than the parent node and left subtree contains values less than the parent node */
    @Test
    void rightViewTest() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(4);
        binarySearchTree.insert(2);
        binarySearchTree.insert(1);
        binarySearchTree.insert(3);
        binarySearchTree.insert(6);
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        BinarySearchTree.rightView(binarySearchTree.root);
        // Expect output: "4 6 7"
    }
}

plugins {
    id("java")
    id("io.freefair.lombok") version "8.13"
}

group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(platform("org.junit:junit-bom:5.10.0"))
    testImplementation("org.junit.jupiter:junit-jupiter")
}

tasks.test {
    useJUnitPlatform()
}

Complexity Analysis

• Time Complexity is O(N) because each node is visited once

• Space Complexity is O(N) For storing nodes in the queue