Print Bottom-Right View of a Binary Tree

In this article, we will address the problem of printing the bottom-right view of a binary tree. The task is to find and print the rightmost elements at each level of the binary tree when viewed from the bottom. To accomplish this, we will employ a depth-first search (DFS) approach to traverse the tree and maintain a record of the rightmost elements at each level.

Problem Statement

Given a binary tree, we aim to print the bottom-right view of the tree. The bottom-right view of a binary tree is the collection of nodes visible when the tree is viewed from the right side at each level. In other words, for each level of the tree, we want to print the rightmost node at that level.

Example

Let's consider a binary tree as an example:

     10
    /  \
   2    4
  /    / \
 3    6   5
       \
        7
      /  \
     8    11

The bottom-right view of this tree is [5, 11, 8] when viewed from the right side at each level, as indicated by the arrows in the tree diagram.

Idea to Solve the Problem

To print the bottom-right view of the binary tree, we can perform a depth-first traversal of the tree while maintaining a record of the rightmost node at each level. We will use a HashMap to store this information, where the key represents the level of the node, and the value is the rightmost node's value at that level. We'll start the traversal from the root node with a distance of 0 and increment the distance when moving to the left child and stay at the same distance when moving to the right child.

Pseudocode

Here is the pseudocode for solving the problem:

function bottomRightView(node, distance, record):
        if node is not null:
            record.put(distance, node.data)
            bottomRightView(node.left, distance + 1, record)
            bottomRightView(node.right, distance, record)
    
    function printBottomRight():
        record = empty HashMap
        bottomRightView(root, 0, record)
        distance = 0
        while distance < size of record:
            print record.get(distance)
            increment distance by 1

Algorithm Explanation

1. Initialize an empty HashMap called record to store the rightmost nodes at each level.
2. Call the bottomRightView function starting from the root node with an initial distance of 0.
3. In the bottomRightView function:
   • If the current node is not null, add the node's data to the record at the current distance.
   • Recursively call the function for the left child with an increased distance (moving left).
   • Recursively call the function for the right child without changing the distance (moving right).
4. After the traversal is complete, iterate through the record map, starting from distance 0, and print the rightmost node's value at each level.
5. Increment the distance by 1 in each iteration until all the rightmost nodes at each level are printed.

Code Solution

1) Bottom right view of binary tree in java 2) Bottom right view of binary tree in c++ 3) Bottom right view of binary tree in c# 4) Bottom right view of binary tree in vb.net 5) Bottom right view of binary tree in php 6) Bottom right view of binary tree in node js 7) Bottom right view of binary tree in python 8) Bottom right view of binary tree in ruby 9) Bottom right view of binary tree in scala 10) Bottom right view of binary tree in swift 11) Bottom right view of binary tree in kotlin 12) Bottom right view of binary tree in golang

Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the depth-first traversal, and the HashMap operations take constant time.