Sort in C++ standard template library
November 14, 2017
Right view of a binary tree
December 7, 2017

Left view of a binary tree

Write code to print the left-view of a binary tree. Left-view of the tree is the nodes visible when the tree is seen from the left side. If there are two nodes at the same level, then only the left-most node will be visible in the left-view as shown below:

Solution:
While traversing the tree in pre-order traversal, we are visiting the left-most node of a particular level before visiting other nodes at that level.
The solution to this problem is simple, we traverse the given tree in pre-order traversal and keep a check on whether or not the left-most node at the current level is printed.
If no nodes for the current level is printed, print the current node, else continue to traverse the tree in pre-order.
We need two variables in this case,

  1. A variable for the current level of node (See this post)
  2. A reference variable for the maximum level upto which the left-most nodes are printed.

Below is the C++ code for this:

struct Node
{
    char data;
    Node* left;
    Node* right;
    Node(int v):data(v), left(NULL), right(NULL){}
};
void printLeftView(Node *r, int level, int* maxLevel)
{
    if(r == NULL){ return; }
    if(level > *maxLevel)
    {
        printf("%c ", r->data);
        *maxLevel = level;
    }
    printLeftView(r->left, level+1, maxLevel);
    printLeftView(r->right, level+1, maxLevel);
}
int main(int argc, const char * argv[]) {
    Node* root = new Node('A');
    root->left = new Node('B');
    root->right = new Node('C');
    root->left->left = new Node('D');
    root->left->right = new Node('E');
    root->right->left = new Node('F');
    root->right->left->right = new Node('G');
    int maxLevel = -1;
    printLeftView(root, 0, &maxLevel);
    return 0;
}

 
 

Leave a Reply

Your email address will not be published. Required fields are marked *