Print the left view of a Binary Tree

Given a binary tree, write a program to print its left view. The left view of a binary tree contains all the nodes that are visible when the tree is viewed from the left side.

Input/Output Examples

plaintext
Example 1:
Input:

     1
    / \
   2   3
  / \   \
 4   5   6

Output:
[1, 2, 4]
Explanation: When viewed from the left side, the visible nodes are 1, 2, and 4.

Example 2:
Input:

     10
    /  \
   20   30
  /
 40

Output:
[10, 20, 40]
Explanation: When viewed from the left side, the visible nodes are 10, 20, and 40.

Approach to Print the Left View of a Binary Tree

  1. Recursive Depth-First Search (DFS) Traversal:
    • Perform a recursive traversal of the binary tree. During the traversal, keep track of the maximum level visited so far.
    • For each node, if the current level is greater than the maximum level visited, add the node's value to the result list and update the maximum level.
  2. Level-Based Check:
    • The idea is to visit each level of the tree and add the first node encountered at each level to the left view.
  3. Edge Case:
    • If the tree is empty, return an empty list.

C++ Program to Print the Left View of a Binary Tree

cpp
#include <iostream>
#include <vector>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Helper function to print the left view of the tree
void leftViewUtil(TreeNode* root, vector<int>& result, int level, int& maxLevel) {
    if (root == NULL) {
        return;
    }

    // If this is the first node of its level
    if (level > maxLevel) {
        result.push_back(root->data);
        maxLevel = level;
    }

    // Recur for the left and right subtrees
    leftViewUtil(root->left, result, level + 1, maxLevel);
    leftViewUtil(root->right, result, level + 1, maxLevel);
}

// Function to print the left view of a binary tree
vector<int> leftView(TreeNode* root) {
    vector<int> result;
    int maxLevel = -1;
    leftViewUtil(root, result, 0, maxLevel);
    return result;
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    // Get and print the left view of the tree
    vector<int> leftViewResult = leftView(root);
    for (int node : leftViewResult) {
        cout << node << " ";
    }
    cout << endl;
    return 0;
}

Java Program to Print the Left View of a Binary Tree

java
import java.util.ArrayList;
import java.util.List;

// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class LeftViewBinaryTree {

    // Helper function to print the left view of the tree
    public static void leftViewUtil(TreeNode root, List<Integer> result, int level, int[] maxLevel) {
        if (root == null) {
            return;
        }

        // If this is the first node of its level
        if (level > maxLevel[0]) {
            result.add(root.data);
            maxLevel[0] = level;
        }

        // Recur for the left and right subtrees
        leftViewUtil(root.left, result, level + 1, maxLevel);
        leftViewUtil(root.right, result, level + 1, maxLevel);
    }

    // Function to print the left view of a binary tree
    public static List<Integer> leftView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        int[] maxLevel = {-1};
        leftViewUtil(root, result, 0, maxLevel);
        return result;
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // Get and print the left view of the tree
        List<Integer> leftViewResult = leftView(root);
        for (int node : leftViewResult) {
            System.out.print(node + " ");
        }
        System.out.println();
    }
}

Python Program to Print the Left View of a Binary Tree

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Helper function to print the left view of the tree
def left_view_util(root, result, level, max_level):
    if root is None:
        return

    # If this is the first node of its level
    if level > max_level[0]:
        result.append(root.data)
        max_level[0] = level

    # Recur for the left and right subtrees
    left_view_util(root.left, result, level + 1, max_level)
    left_view_util(root.right, result, level + 1, max_level)

# Function to print the left view of a binary tree
def left_view(root):
    result = []
    max_level = [-1]
    left_view_util(root, result, 0, max_level)
    return result

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    # Get and print the left view of the tree
    left_view_result = left_view(root)
    print("Left View:", left_view_result)
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once during the recursive traversal.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case (for a skewed tree), the space complexity is O(n).

DSA

7330

487

Related Articles