Posted on by Kalkicode
Code Binary Tree

Print right view of a binary tree

The problem involves printing the right view of a binary tree. The right view of a binary tree consists of all the nodes that are visible when looking at the tree from the right side, starting from the root and proceeding to the deepest level.

Right view of BST

Problem Statement and Description

Given a binary tree, the task is to write a program that prints the nodes that are visible from the right side of the tree. This means that for each level of the tree, only the rightmost node at that level should be considered for printing.

Example

Consider the following binary tree:


         1
       /   \
      2     3
     /     / \
    4     5   6
   /       \
  7         8
           /
          9

The right view of this tree is [1, 3, 6, 8, 9]. These are the nodes that would be visible when looking at the tree from the right side.

Idea to Solve the Problem

To solve this problem, we can follow these steps:

  1. Traverse the binary tree using Depth-First Search (DFS).
  2. During the traversal, for each level, only consider the last node encountered (rightmost node) and print its value.
  3. Maintain a variable (level) to keep track of the current level.
  4. If the level is higher than the previous highest level, print the node's value and update the level.
  5. Recursively visit the right subtree first, then the left subtree.

Standard Pseudocode

Here's a high-level pseudocode representation of the algorithm to print the right view of a binary tree:

PrintRightView(node, depth):
    if node is NULL:
        return
    
    if depth is greater than current level:
        print node's value
        update current level
        
    Recursively visit right subtree with increased depth
    Recursively visit left subtree with increased depth

Algorithm Explanation

  1. Traverse the binary tree in a Depth-First Search (DFS) manner.
  2. For each node encountered, if the current depth is greater than the level, print the node's value and update the level.
  3. Recursively visit the right subtree with an increased depth.
  4. Recursively visit the left subtree with an increased depth.

Code Solution

Time Complexity

The time complexity of the provided code is determined by the DFS traversal of the binary tree. In the worst case, where the binary tree is completely unbalanced (resembling a linked list), the algorithm's time complexity is O(n), where 'n' is the number of nodes in the tree.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment