Skip to main content

Left/Right View of Binary Tree

Problem Statement:​

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Explanation:

Example 2:

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Explanation:

  • Example:

✅ Solution 1: Left View (Recursive DFS)​

class Solution {
public:
    void collectLeftView(TreeNode* node, int level, vector<int>& view) {
        if (!node) return;

        // Add the first node at this level
        if (view.size() == level) {
            view.push_back(node->val);
        }

        // Traverse left first to ensure leftmost is picked
        collectLeftView(node->left, level + 1, view);
        collectLeftView(node->right, level + 1, view);
    }

    vector<int> leftSideView(TreeNode* root) {
        vector<int> leftView;
        collectLeftView(root, 0, leftView);
        return leftView;
    }
};

✅ Solution 2: Right View (Recursive DFS)​

class Solution {
public:
    void collectRightView(TreeNode* node, int level, vector<int>& view) {
        if (!node) return;

        // Add the first node at this level
        if (view.size() == level) {
            view.push_back(node->val);
        }

        // Traverse right first to ensure rightmost is picked
        collectRightView(node->right, level + 1, view);
        collectRightView(node->left, level + 1, view);
    }

    vector<int> rightSideView(TreeNode* root) {
        vector<int> rightView;
        collectRightView(root, 0, rightView);
        return rightView;
    }
};

✅ Solution 3: Left View (Iterative BFS)​

class Solution {
public:
    vector<int> leftSideView(TreeNode* root) {
        vector<int> leftView;
        if (!root) return leftView;

        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* current = nodeQueue.front();
                nodeQueue.pop();

                if (i == 0) leftView.push_back(current->val); // first node at this level

                if (current->left) nodeQueue.push(current->left);
                if (current->right) nodeQueue.push(current->right);
            }
        }
        return leftView;
    }
};

✅ Solution 4: Right View (Iterative BFS)​

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> rightView;
        if (!root) return rightView;

        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* current = nodeQueue.front();
                nodeQueue.pop();

                if (i == levelSize - 1) rightView.push_back(current->val); // last node at this level

                if (current->left) nodeQueue.push(current->left);
                if (current->right) nodeQueue.push(current->right);
            }
        }
        return rightView;
    }
};

📝 How It Works​

  • In DFS, we keep track of the level during recursion.
    • For left view, go left first and record the first node seen at that level.
    • For right view, go right first and do the same.
  • In BFS, we use level-order traversal.
    • For left view, pick the first node in each level.
    • For right view, pick the last node in each level.

🧩 Key Observation​

  • Use a queue for BFS.
  • Use recursion + level for DFS.
  • For any side view: track the first/last node at each level.

⏱️ Time & Space Complexity​

ApproachTimeSpace
DFS (left/right)O(N)O(H)
BFS (left/right)O(N)O(W)

Where:

  • N is total number of nodes
  • H is tree height (recursion stack)
  • W is tree width (queue size)

⚠️ Edge Cases​

  • Empty tree → returns an empty vector.
  • Skewed trees (left/right) → returns all nodes linearly.
  • Multiple nodes at same depth → only one (first/last) considered depending on view.

🔁 Related Problems​

  • Top View of Binary Tree
  • Bottom View of Binary Tree
  • Vertical Order Traversal
  • Diagonal Traversal
💬

Discussion & Doubts