Binary Side View

Binary Side View

Let's solve the problem of obtaining the right side view of a binary tree.

To achieve that, here's a breakdown of how the pseudocode works:

Code Implementation

import collections

class SolutionOne:
    def binary_Side_view(self, root):
        """
        Obtain the values of nodes visible from the right side of a binary tree.

        Args:
            root: The root node of the binary tree.

        Returns:
            list: A list containing the values of nodes visible from the right side of the binary tree.

        Example:
            # Create a binary tree
            #      1
            #     / \
            #    2   3
            #     \   \
            #      5   4
            root = TreeNode(1)
            root.left = TreeNode(2)
            root.right = TreeNode(3)
            root.left.right = TreeNode(5)
            root.right.right = TreeNode(4)

            # Instantiate the solution object
            solution = SolutionOne()

            # Obtain the values of nodes visible from the right side of the binary tree
            right_side_view = solution.binary_Side_view(root)

            print("Right side view of the binary tree:", right_side_view)
        """
        # Initialize a deque with the root node
        q = collections.deque([root])
        
        # Initialize an empty list to store the values of nodes visible from the right side
        res = []
        
        # While there are still nodes in the deque
        while q:
            # For each level of the tree
            for _ in range(len(q)):
                # Initialize a variable to keep track of the rightmost node at this level
                rightSide = None
                
                # Pop nodes from the left side of the deque
                node = q.popleft()
                
                # If the node exists
                if node:
                    # Update the rightmost node for this level
                    rightSide = node
                    
                    # Add the left child of the node to the deque if it exists
                    if node.left:
                        q.append(node.left)
                    
                    # Add the right child of the node to the deque if it exists
                    if node.right:
                        q.append(node.right)
                        
            # If there was a rightmost node at this level, append its value to the result list
            if rightSide:
                res.append(rightSide.val)
        
        # Return the list containing the values of nodes visible from the right side of the binary tree
        return res

The binary_Side_view function takes a binary tree root node as input and aims to return a list containing the values of nodes visible from the right side of the tree.

In other words, it's traversing the binary tree level by level, and for each level, it only keeps track of the rightmost node encountered. After traversing all levels, it returns the values of these rightmost nodes.

Time Complexity

The algorithm traverses each node of the binary tree once.

At each node, the algorithm performs constant time operations such as appending nodes to the deque and popping nodes from the deque.

Therefore, the time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree.

Space Complexity

The algorithm utilizes a deque to perform level order traversal of the binary tree.

In the worst-case scenario, the deque may contain all nodes at a particular level of the binary tree.

Therefore, the space complexity of the algorithm is O(W), where W is the maximum width of the binary tree. In the worst case, the width of the binary tree can be N/2, where N is the total number of nodes in the binary tree. Hence, the space complexity can also be considered as O(N).

Unit Tests

We will use Python's built-in unittest module to write unit tests for the solution. Here's how you can structure the unit tests to test the correctness and robustness of the solution above:

import unittest

class TestSolutionOne(unittest.TestCase):
    def setUp(self):
        # Define a helper function to create a binary tree node
        class TreeNode:
            """TreeNode class Structure"""
            def __init__(self, val=0, left =None, right=None):
                self.val    = val
                self.left   = left
                self.right  = right
        
        # Create a sample binary tree
        #      1
        #     / \
        #    2   3
        #     \   \
        #      5   4
        self.tree = TreeNode(1)
        self.tree.left = TreeNode(2)
        self.tree.right = TreeNode(3)
        self.tree.left.right = TreeNode(5)
        self.tree.right.right = TreeNode(4)
        
        # Instantiate the solution object
        self.solution = SolutionOne()

    def test_correctness(self):
        # Expected right side view of the binary tree: [1, 3, 4]
        expected_right_side_view = [1, 3, 4]
        # Obtain the actual right side view using the solution
        actual_right_side_view = self.solution.binary_side_view(self.tree)
        # Assert that the actual result matches the expected result
        print(f"actual_right_side_view:: {actual_right_side_view}")
        self.assertEqual(actual_right_side_view, expected_right_side_view)

    def test_robustness(self):
        # Test with an empty binary tree
        empty_root = None
        # Expected right side view of the empty binary tree: []
        expected_empty_right_side_view = []
        # Obtain the actual right side view using the solution
        actual_empty_right_side_view = self.solution.binary_side_view(empty_root)
        # Assert that the actual result matches the expected result for the empty tree
        self.assertEqual(actual_empty_right_side_view, expected_empty_right_side_view)

if __name__ == '__main__':
    unittest.main()

In this test suite, we test test_correctness and  test_robustness.

The setUp is called before each test method, and it's used to set up any necessary objects or configurations for the tests.

The aim is to verify whether the solution produces the correct output for a sample binary tree and how it handles edge cases like an empty binary tree correctly.