Given a binary tree, how do we print the left view of it?
For example, consider the simple binary tree below
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |