Left View of Binary Tree

Given a Binary Tree, return Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument. If no left view is possible, return an empty tree.

Left view of following tree is 1 2 4 8.

          1
       /     \
     2        3
   /     \    /    \
  4     5   6    7
   \
     8   

Examples :

Input:
   1
 /  \
3    2
Output: 1 3

Input:

Output: 10 20 40

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
0 <= Number of nodes <= 10⁵
0 <= Data of a node <= 10⁵

Approach 01:

vector<int> result;

void findLeftView(Node* root, int& maxLevel, int currentLevel) {
    if (root == nullptr) {
        return;
    }
    if (maxLevel < currentLevel) {
        result.push_back(root->data);
        maxLevel = currentLevel;
    }
    findLeftView(root->left, maxLevel, currentLevel + 1);
    findLeftView(root->right, maxLevel, currentLevel + 1);
}

vector<int> leftView(Node* root) {
    result.clear();
    int maxLevel = 0;
    findLeftView(root, maxLevel, 1);
    return result;
}

def findLeftView(root, maxLevel, currentLevel, result):
    if not root:
        return
    
    if maxLevel[0] < currentLevel:
        result.append(root.data)
        maxLevel[0] = currentLevel
    
    findLeftView(root.left, maxLevel, currentLevel + 1, result)
    findLeftView(root.right, maxLevel, currentLevel + 1, result)

def LeftView(root):
    result = []
    maxLevel = [0]
    findLeftView(root, maxLevel, 1, result)
    return result

Time Complexity

• Tree Traversal:

  The function performs a depth-first search (DFS) to traverse the tree. In the worst case, all nodes in the tree are visited once, leading to a time complexity of \( O(\text{numNodes}) \), where \( \text{numNodes} \) is the number of nodes in the tree.

• Overall Time Complexity:

  The overall time complexity is \( O(\text{numNodes}) \).

Space Complexity

• Auxiliary Space:

  The space required for the recursion stack depends on the height of the tree. In the worst case (a skewed tree), the recursion stack can go as deep as the number of nodes, which gives a space complexity of \( O(\text{numNodes}) \). In a balanced tree, the height would be \( O(\log \text{numNodes}) \), resulting in \( O(\log \text{numNodes}) \) space for the stack.

• Result Vector:

  The result vector stores the nodes in the left view, which can take up to \( O(\text{height}) \) space, where \( \text{height} \) is the height of the tree.

• Overall Space Complexity:

  In the worst case, the overall space complexity is \( O(\text{numNodes}) \) due to the recursion stack. For a balanced tree, it is \( O(\log \text{numNodes}) \).