Close

Left view of a binary tree

Given a binary tree, how do we print the left view of it?

For example, consider the simple binary tree below

   1
 /
2   3

The left view of this is 1, 2. Similarly consider one more example

            1
          / 
         2    3
             /
            4   5

Left view for this tree contains 1, 2, 4.

If the tree is completely left skewed or right skewed, the left view contains all the nodes like the following. For example

1                1
               /
  2            2
             /
    3        3

The left view for both of the above trees is 1, 2, 3.

We can solve this problem in two ways, one iterative and the other using recursion.

Recursive method:

In this approach to the traversal function, we send two additional parameters along with root node, one is the current level and another is maximum level. maximum level is a reference parameter which remembers it’s value between the function calls. 
We compare the current and maximum level values, if the max level is less than current level we print the data at root node and update the maximum level. Recursively call the same function for the left and right sub-trees by incrementing the current level.


Iterative method:

We use the level order traversal method to print the first node in each level. While storing the nodes in the queue, we store a separator (NULL) node to distinguish between the levels.


Here is the C++ code which implements the above approaches.Both run in O(n) time complexity.

#include <iostream>
#include <queue>
using namespace std;
//Binary tree node type
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int v):val(v),left(NULL), right(NULL)
{
}
};
//Binary search tree insert procedure for creating binary tree to test
TreeNode* insert(TreeNode * root, int data)
{
if( root == NULL )
{
root = new TreeNode(data);
return root;
}
if( data < root->val )
root->left = insert( root->left, data );
else
root->right = insert( root->right, data );
return root;
}
//Use level order traversing to find out the first node in each level
//nodes at a particular level in the queue are separated by NULL node
void printLeftView(TreeNode *root)
{
if( root == NULL )
return;
queue<TreeNode*> nodeQ;
nodeQ.push(root);
nodeQ.push(NULL);
cout << root->val << " ";
while( !nodeQ.empty() )
{
TreeNode *temp = nodeQ.front();
nodeQ.pop();
if( temp == NULL )
{
if( !nodeQ.empty() )
{
temp = nodeQ.front();
cout << temp->val << " ";
nodeQ.pop();
nodeQ.push(NULL);
}
}
if( temp != NULL )
{
if( temp->left != NULL )
nodeQ.push(temp->left);
if( temp->right != NULL )
nodeQ.push(temp->right);
}
}
cout << endl;
}
void printLeftViewRecursive(TreeNode *root, int &maxLevel, int currentLevel)
{
if( root == NULL )
return;
if( maxLevel < currentLevel )
{
cout << root->val << " ";
maxLevel = currentLevel;
}
printLeftViewRecursive( root->left, maxLevel, currentLevel+1 );
printLeftViewRecursive( root->right, maxLevel, currentLevel+1 );
}
void leftViewRecursive(TreeNode *root)
{
int maxLevel = -1;
printLeftViewRecursive(root, maxLevel, 0);
}
void Test1()
{
TreeNode *root = NULL;
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 4);
root = insert(root, 3);
root = insert(root, 5);
printLeftView(root);
leftViewRecursive(root);
cout << endl;
}
void Test2()
{
TreeNode *root = NULL;
root = insert(root, 4);
root = insert(root, 2);
root = insert(root, 5);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 6);
printLeftView(root);
leftViewRecursive(root);
cout << endl;
}
int main()
{
Test1();
Test2();
return 0;
}

Leave a Reply

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