Given a binary tree, write an efficient algorithm to print left view of binary tree.

### 1. Iterative implementation –

In iterative version, we perform level order traversal of the tree. We can modify level order traversal to maintain nodes in current level. Then if current node is first node of current level, we print it.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Iterative function to print left view of given binary tree void leftView(Node* root) { // return if tree is empty if (root == nullptr) return; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // pointer to store current node Node* curr = nullptr; // run till queue is not empty while (!queue.empty()) { // calculate number of nodes in current level int size = queue.size(); int i = 0; // process every node of current level and enqueue their // non-empty left and right child to queue while (i++ < size) { curr = queue.front(); queue.pop_front(); // if this is first node of current level, print it if (i == 1) cout << curr->key << " "; if (curr->left) queue.push_back(curr->left); if (curr->right) queue.push_back(curr->right); } } } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

### 2. Recursive implementation using Hashing –

We can also solve this problem by using Hashing. The idea is to traverse the tree in preorder fashion and pass level information in function arguments. If the level is visited for the first time, then we insert the current node and level information into the map. Finally when all nodes are processed, we traverse the map and print the left view.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // traverse nodes in pre-order fashion void leftView(Node *root, int level, auto &map) { if (root == nullptr) return; // if level is visited for the first time, insert the current node // and level information into the map if (map.find(level) == map.end()) map[level] = root->key; leftView(root->left, level + 1, map); leftView(root->right, level + 1, map); } // Function to print left view of given binary tree int leftView(Node *root) { // create an empty map to store first node for each level map<int, int> map; // traverse the tree and fill map leftView(root, 1, map); // iterate through the map and print left view for (auto it: map) cout << it.second << " "; } |

We can also traverse nodes in reverse pre-order fashion as shown below:

1 2 3 4 5 6 7 8 9 10 11 12 |
void leftView(Node *root, int level, auto &map) { if (root == nullptr) return; // insert the current node and level information into the map map[level] = root->key; // recurse for right subtree before left subtree leftView(root->right, level + 1, map); leftView(root->left, level + 1, map); } |

The time complexity of above solution is O(nlog(n)) and auxiliary space used by the program is O(n).

### 3. Recursive implementation using Preorder traversal –

We can also solve this problem by using constant space and in linear time. The idea is to traverse the tree in preorder fashion and maintain maximum level visited so far. If current level is more than maximum level visited so far, then the current node is the first node of current level and we print it and also update last level to current level.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Recursive function to print left view of given binary tree void leftView(Node *root, int level, int &last_level) { // base case: empty tree if (root == nullptr) return; // if current node is first node of current level if (last_level < level) { // print the node's data cout << root->key << " "; // update last level to current level last_level = level; } // recurse for left and right subtree by increasing level by 1 leftView(root->left, level + 1, last_level); leftView(root->right, level + 1, last_level); } // Function to print left view of given binary tree void leftView(Node *root) { int last_level = 0; leftView(root, 1, last_level); } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

**Exercise:** Print Right View of a Binary Tree

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

I dont see how the hashing is O(nlogn). I think it is still O(N), N is the total number of nodes.