Different Views Of Binary Tree

Different Views of a Binary Tree refer to the various ways in which we can visualize and extract information from a binary tree. There are three common views: top view, bottom view, and left view. Each view provides a different perspective on the binary tree.

Example: Let's create a binary tree and demonstrate the top view, bottom view, and left view.

# Node class definition
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(4)
root.left.right.right = Node(5)
root.left.right.right.right = Node(6)

# Top view of the binary tree
def top_view(root):
    if root is None:
        return

    # Create a dictionary to store the horizontal distance of each node from the root
    hd_dict = {}
    # Create a queue to perform level order traversal
    queue = [(root, 0)]

    while queue:
        node, hd = queue.pop(0)

        # Only store the first node encountered at each horizontal distance
        if hd not in hd_dict:
            hd_dict[hd] = node.value

        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))

    # Print the nodes in the top view based on their horizontal distance
    top_view_nodes = [hd_dict[hd] for hd in sorted(hd_dict.keys())]
    print("Top view:", top_view_nodes)

top_view(root)
# Output: 2 1 3

# Bottom view of the binary tree
def bottom_view(root):
    if root is None:
        return

    # Create a dictionary to store the horizontal distance and value of each node
    hd_dict = {}
    # Create a queue to perform level order traversal
    queue = [(root, 0)]

    while queue:
        node, hd = queue.pop(0)

        # Update the horizontal distance and value of the current node in the dictionary
        hd_dict[hd] = node.value

        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))

    # Print the nodes in the bottom view based on their horizontal distance
    bottom_view_nodes = [hd_dict[hd] for hd in sorted(hd_dict.keys())]
    print("Bottom view:", bottom_view_nodes)

bottom_view(root)
# Output: 2 4 6 3

# Left view of the binary tree
def left_view(root):
    if root is None:
        return

    # Create a list to store the nodes at each level
    level_nodes = []
    # Create a queue to perform level order traversal
    queue = [root]

    while queue:
        level_length = len(queue)
        level_nodes.append(queue[0].value)  # Add the first node of each level to the list

        for _ in range(level_length):
            node = queue.pop(0)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    print("Left view:", level_nodes)

left_view(root)
# Output: 1 2 4 6

In this example, we define a Node class that represents a node in the binary tree. Each node has a value, left child, and right child.

We create a binary tree with the given values.

Top View: The top view of a binary tree refers to the nodes that are visible from the top when we look down the tree. To obtain the top view, we perform a level order traversal of the tree and maintain a dictionary (hd_dict) to store the first node encountered at each horizontal distance (hd). We use a queue to perform the level order traversal. At each node, we update the dictionary only if the horizontal distance is not already present in the dictionary. Finally, we print the nodes from the dictionary based on their horizontal distance.

Bottom View: The bottom view of a binary tree refers to the nodes that are visible from the bottom when we look up the tree. The approach to obtaining the bottom view is similar to the top view. We perform a level order traversal and update the dictionary (hd_dict) with the current node's value at each horizontal distance (hd). Since we traverse the tree in a level order manner, the last node encountered at each horizontal distance would be the one visible from the bottom. Finally, we print the nodes from the dictionary based on their horizontal distance.

Left View: The left view of a binary tree refers to the nodes that are visible from the left side of the tree. To obtain the left view, we perform a modified level order traversal. Instead of maintaining a dictionary, we maintain a list (level_nodes) to store the nodes at each level. At each level, we add the value of the first node encountered to the list. This way, the nodes at each level are visible from the left. Finally, we print the nodes from the list.

The time complexity of each view operation is O(n), where n is the number of nodes in the binary tree, as we need to visit each node once. The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree, as we store the nodes at each level in a data structure (dictionary or list).

Right View: The right view of a binary tree refers to the nodes that are visible from the right side of the tree. The approach to obtaining the right view is similar to the left view. We perform a modified level order traversal, but this time we add the value of the last node encountered at each level to the list. This way, the nodes at each level are visible from the right. Finally, we print the nodes from the list.

# Right view of the binary tree
def right_view(root):
    if root is None:
        return

    # Create a list to store the nodes at each level
    level_nodes = []
    # Create a queue to perform level order traversal
    queue = [root]

    while queue:
        level_length = len(queue)
        level_nodes.append(queue[-1].value)  # Add the last node of each level to the list

        for _ in range(level_length):
            node = queue.pop(0)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    print("Right view:", level_nodes)

right_view(root)
# Output: 1 3 7

In the example, we add the right_view function to obtain the right view of the binary tree. The implementation is similar to the left view, but instead of adding the first node encountered at each level, we add the last node encountered (queue[-1]) to the level_nodes list.

The time complexity of the right view operation is also O(n), where n is the number of nodes in the binary tree, as we need to visit each node once. The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree, as we store the nodes at each level in a list.

By using these different views of a binary tree, we can gain insights into the structure and visibility of the tree from different perspectives. These views can be helpful in analyzing and understanding the characteristics of a binary tree in various scenarios.

Let's solve a question related to the different views of a binary tree. The question is "Binary Tree Right Side View," which asks for the right view of a binary tree.

Problem Statement: Given the root of a binary tree, imagine you are standing on the right side of it and return the values of the nodes you can see ordered from top to bottom.

Example:

# Node class definition
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Function to obtain the right side view of a binary tree
def right_side_view(root):
    if root is None:
        return []

    right_view = []
    queue = [root]

    while queue:
        level_length = len(queue)
        right_view.append(queue[-1].value)

        for _ in range(level_length):
            node = queue.pop(0)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return right_view

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.right.right = Node(4)

# Obtain the right side view of the binary tree
result = right_side_view(root)
print(result)
# Output: [1, 3, 4]

In this solution, we define a Node class that represents a node in the binary tree. Each node has a value, left child, and right child.

We define the right_side_view function that takes the root of the binary tree as input and returns the right side view of the tree as a list.

Inside the function, we handle the base case where the root is None, in which case we return an empty list.

We initialize an empty list right_view to store the right side view and a queue queue to perform level order traversal.

We iterate over the levels of the binary tree using a while loop that continues until the queue is empty. At each level, we get the length of the queue, which represents the number of nodes in that level.

We append the value of the last node in the level (the rightmost node) to the right_view list.

Next, we iterate level_length times to process each node in the current level. We remove the node from the left end of the queue and enqueue its left and right child nodes if they exist.

Finally, we return the right_view list, which contains the values of the nodes visible from the right side of the binary tree.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, as we need to visit each node once. The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree, as we store the nodes at each level in the queue.

Different Views Of Binary Tree

DIFFICULTY

COMPANY

Data Structures