Binary Tree Right Side View
Statement
Given the root of a binary tree with n number of nodes, return the right-side view as a list. The right-side view of a binary tree is the nodes that are visible when the tree is viewed from the right side.
Constraints
- 0 ≤
n≤ 100 - -100 ≤
node.data≤ 100
Solution
"""
production algorithm
"""
from collections import defaultdict
class Solution:
def right_side_view(self, root):
"""
time complexity O(n)
space complexity O(n)
"""
indexer = defaultdict(int)
self.right_side_view_helper(root, indexer, 0)
n = len(indexer)
return [indexer[i] for i in range(n)]
def right_side_view_helper(self, root, indexer, n):
"""
time complexity O(n)
space complexity O(n)
"""
if root is None:
return
indexer[n] = root.data
self.right_side_view_helper(root.left, indexer, n + 1)
self.right_side_view_helper(root.right, indexer, n + 1)"""
unit tests
"""
from unittest import TestCase
from algorithms.dfs.binary_tree_right_side_view.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class SolutionTestCase(TestCase):
def test_balanced_tree(self):
# Given
root = BinaryTreeNode(-1)
root.left = BinaryTreeNode(-7)
root.right = BinaryTreeNode(10)
root.left.left = BinaryTreeNode(-9)
root.left.right = BinaryTreeNode(-4)
root.right.left = BinaryTreeNode(6)
root.right.right = BinaryTreeNode(16)
root.left.left.left = BinaryTreeNode(-18)
root.left.left.right = BinaryTreeNode(-8)
root.left.right.left = BinaryTreeNode(-6)
root.left.right.right = BinaryTreeNode(-3)
root.right.left.left = BinaryTreeNode(3)
root.right.left.right = BinaryTreeNode(9)
root.right.right.left = BinaryTreeNode(11)
root.right.right.right = BinaryTreeNode(18)
solution = Solution()
# When
actual = solution.right_side_view(root)
# Then
expected = [-1, 10, 16, 18]
self.assertEqual(actual, expected)
def test_left_skewed_tree(self):
# Given
root = BinaryTreeNode(10)
root.left = BinaryTreeNode(-4)
root.right = BinaryTreeNode(16)
root.left.left = BinaryTreeNode(-8)
root.left.right = BinaryTreeNode(3)
root.right.left = BinaryTreeNode(11)
root.right.right = BinaryTreeNode(18)
root.left.left.left = BinaryTreeNode(-9)
root.left.left.right = BinaryTreeNode(-6)
root.left.right.left = BinaryTreeNode(-1)
root.left.right.right = BinaryTreeNode(9)
root.left.left.left.left = BinaryTreeNode(-18)
root.left.left.right.left = BinaryTreeNode(-7)
root.left.right.left.left = BinaryTreeNode(-3)
root.left.right.right.left = BinaryTreeNode(6)
solution = Solution()
# When
actual = solution.right_side_view(root)
# Then
expected = [10, 16, 18, 9, 6]
self.assertEqual(actual, expected)
def test_degenerate_tree(self):
# Given
root = BinaryTreeNode(-1)
root.left = BinaryTreeNode(3)
root.left.right = BinaryTreeNode(6)
root.left.right.left = BinaryTreeNode(9)
root.left.right.left.right = BinaryTreeNode(10)
root.left.right.left.right.left = BinaryTreeNode(11)
root.left.right.left.right.left.right = BinaryTreeNode(16)
root.left.right.left.right.left.right.left = BinaryTreeNode(18)
solution = Solution()
# When
actual = solution.right_side_view(root)
# Then
expected = [-1, 3, 6, 9, 10, 11, 16, 18]
self.assertEqual(actual, expected)Strategy
Depth First Search.
Explanation
The right-side view of a binary tree is easily found through a preorder traversal of a given binary tree. Recall, that the order of steps of a preorder traversal is root, left, and then right. By tracking the level of the binary tree during traversal, the right-side view of a level can be updated as further and further right nodes of the tree are met trough preorder traversal.
Time Complexity
Every node of the binary tree is visited once. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
In the case of a degenerate tree, the depth of recursion of preorder traversal is n, where n is the number of nodes in the tree. Therefore, the auxiliary space complexity of the algorithm is O(n).
