Left View Of Binary Tree
Print left view of Binary Tree

Question

Left View Of Binary Tree

Print left view of Binary Tree

Accepted Answer

Recursive Approach

This problem can be solved through recursion.We will maintain max_level variable which will keep track of maxLevel and will pass current level in recursion as argument. Whenever we see a node whose current level is more than maxLevel then we will print that node as that will be first node for that current level. Also update maxLevel with current level.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the binary tree.

Since there can be O(height) nodes in the recursive call stack and in the case of the skewed tree there can be O(N) nodes in the call stack, So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the tree.

Since we are doing a recursive traversal of the tree, the overall time complexity will be O(N).

Accepted Answer

Level Order Traversal

Do level order traversal of the tree using a queue, and we can modify that to maintain nodes at the current level, so if the current node is the first node of the current level then just print it.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the binary tree.

Since we are doing a level-order traversal of the tree and storing the nodes of the levels in a queue. And in the case of a full binary tree, there will be O(N) nodes in the last level. So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the tree.

Since we are doing a level-order traversal of the tree, the overall time complexity will be O(N).

Top Airtel Africa Software Developer interview questions & answers

Popular interview questions of Software Developer