Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

binary
tree
left
view
recursive

How to print the left view of a binary tree

Educative Answers Team

Printing the left view of a binary tree involves printing the left-most node, at each level, in the binary tree.

%0 node_1 1 node_2 2 node_1->node_2 node_3 4 node_1->node_3 node_1563340791191 11 node_2->node_1563340791191 node_1563340762315 15 node_1563340791191->node_1563340762315 node_1563340744558 9 node_3->node_1563340744558 node_1563340766139 3 node_3->node_1563340766139
Left view of a Binary tree; the nodes highlighted in orange are the tree's left view.

Printing the left view of the Binary tree, given above, would involve printing the nodes: 1,2,11,1, 2, 11, and 1515.

Algorithm

This problem is solved by recursively traversing each level in the tree(visiting the left node before the right node). Whenever we move to the next level, print the leftmost node in that level (Note: we traverse the left subtree before the right subtree). The variable maxlevel is used to track the maximum level in the tree that is traversed so far. Each time a node with a level greater than maxlevel is encountered, its value is printed, ​and the value of maxlevel is updated to that value.

Implementation

#include <bits/stdc++.h> 
using namespace std; 
  
class node { 
public: 
  int data; 
  node *left, *right; 
}; 
  
// A function to create a new node in the tree
node* newNode(int item) 
{ 
  node* temp = new node(); 
  temp->data = item; 
  temp->left = temp->right = NULL; 
  return temp; 
} 
  
// Recursive function to print left view of a binary tree.
// It takes a root, the current level, and 
// the max level so far of the binary tree
void leftViewUtil(node* root, int level, int* max_level) 
{ 
  if (root == NULL) 
    return; 

  // If we are moving to a new level, print the first node(left-most)
  if (*max_level < level) { 
    cout << root->data << "\t"; 
    *max_level = level; 
  } 

  leftViewUtil(root->left, level + 1, max_level); 
  leftViewUtil(root->right, level + 1, max_level); 
} 
  
void leftView(node* root) 
{ 
  int max_level = 0; 
  leftViewUtil(root, 1, &max_level); 
} 
  
// Driver code 
int main() 
{
  // creating the tree.
  node* root = newNode(1); 
  root->left = newNode(2); 
  root->right = newNode(4); 
  root->left->left = newNode(11); 
  root->left->left->right = newNode(15); 
  root->right->left = newNode(9); 
  root->right->right = newNode(3); 

  leftView(root); 

  return 0; 
} 

RELATED TAGS

binary
tree
left
view
recursive
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring