Posted on by Kalkicode
Code Binary Tree

Print left view of a binary tree

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

Print left view of a binary tree

Problem Statement and Description

Given a binary tree, the task is to write a program to print the nodes that are visible from the left side of the tree. This means that for each level of the tree, only the leftmost 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 left view of this tree is [1, 2, 4, 7, 9]. These are the nodes that would be visible when looking at the tree from the left 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 first node encountered (leftmost 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 left subtree first, then the right subtree.

Standard Pseudocode

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

PrintLeftView(node, depth):
    if node is NULL:
        return
    
    if depth is greater than current level:
        print node's value
        update current level
        
    Recursively visit left subtree with increased depth
    Recursively visit right 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 left subtree with an increased depth.
  4. Recursively visit the right 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