← Back to DSA Course | Chapter 11: Trees | Lesson 9 of 10

Tree Views यानि Left, Right, Top, Bottom

Tree views एक tree को left, right, top या bottom से देखने और सिर्फ उस side से दिखने वाली branches नोट करने जैसा है।

In this page:

  1. Left View
  2. Right View
  3. Top View
  4. Bottom View
  5. View Practice
Syntax
markup 
from collections import deque
queue = deque([root])
while queue:
    size = len(queue)
    for i in range(size):
        node = queue.popleft()
        if i == 0:
            left_view.append(node.value)    # first node of level
        # enqueue children

Left View

किसी tree का left view हर level से left side से देखने पर दिखने वाला पहला node list करता है — यह हर depth पर मिलने वाला leftmost node है, प्रति level एक।

उदाहरण: Left View

#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
    Node root={1,&l,&r};
    queue<Node*> q; q.push(&root);
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            Node* node = q.front(); q.pop();
            if (i == 0) cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return 0;
}
import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2); root.right = new Node(3);
        Queue<Node> q = new LinkedList<>(); q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                Node node = q.poll();
                if (i == 0) System.out.print(node.val + " ");
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
    }
}
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

root = Node(1)
root.left = Node(2); root.right = Node(3)
q = deque([root])
while q:
    n = len(q)
    for i in range(n):
        node = q.popleft()
        if i == 0:
            print(node.val, end=" ")
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* q[10]; int head=0, tail=0;
int main() {
    struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
    struct Node root={1,&l,&r};
    q[tail++] = &root;
    while (head < tail) {
        int n = tail - head;
        for (int i = 0; i < n; i++) {
            struct Node* node = q[head++];
            if (i == 0) printf("%d ", node->val);
            if (node->left) q[tail++] = node->left;
            if (node->right) q[tail++] = node->right;
        }
    }
    return 0;
}

Right View

Right view left view का mirror है: हर level से right side से देखने पर दिखने वाला आखिरी node, मतलब हर depth पर मिलने वाला rightmost node।

उदाहरण: Right View

#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
    Node root={1,&l,&r};
    queue<Node*> q; q.push(&root);
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            Node* node = q.front(); q.pop();
            if (i == n - 1) cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return 0;
}
import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2); root.right = new Node(3);
        Queue<Node> q = new LinkedList<>(); q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                Node node = q.poll();
                if (i == n - 1) System.out.print(node.val + " ");
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
    }
}
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

root = Node(1)
root.left = Node(2); root.right = Node(3)
q = deque([root])
while q:
    n = len(q)
    for i in range(n):
        node = q.popleft()
        if i == n - 1:
            print(node.val, end=" ")
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* q[10]; int head=0, tail=0;
int main() {
    struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
    struct Node root={1,&l,&r};
    q[tail++] = &root;
    while (head < tail) {
        int n = tail - head;
        for (int i = 0; i < n; i++) {
            struct Node* node = q[head++];
            if (i == n - 1) printf("%d ", node->val);
            if (node->left) q[tail++] = node->left;
            if (node->right) q[tail++] = node->right;
        }
    }
    return 0;
}

Top View

Top view हर horizontal distance पर root से मिलने वाला पहला node list करता है जब tree को एक horizontal line पर project किया जाता है — एक-दूसरे के ठीक ऊपर या नीचे वाले nodes (same horizontal distance) सिर्फ उनका topmost दिखाते हैं।

उदाहरण: Top View

#include <iostream>
#include <map>
using namespace std;
struct Node { int val; Node *left, *right; };
void topView(Node* n, int hd, map<int,int>& seen) {
    if (!n) return;
    if (seen.find(hd) == seen.end()) seen[hd] = n->val;
    topView(n->left, hd - 1, seen);
    topView(n->right, hd + 1, seen);
}
int main() {
    Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
    Node root={1,&l,&r};
    map<int,int> seen;
    topView(&root, 0, seen);
    for (auto& p : seen) cout << p.second << " ";
    return 0;
}
import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void topView(Node n, int hd, TreeMap<Integer,Integer> seen) {
        if (n == null) return;
        seen.putIfAbsent(hd, n.val);
        topView(n.left, hd - 1, seen);
        topView(n.right, hd + 1, seen);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2); root.right = new Node(3);
        TreeMap<Integer,Integer> seen = new TreeMap<>();
        topView(root, 0, seen);
        for (int v : seen.values()) System.out.print(v + " ");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def top_view(n, hd, seen):
    if n is None:
        return
    if hd not in seen:
        seen[hd] = n.val
    top_view(n.left, hd - 1, seen)
    top_view(n.right, hd + 1, seen)

root = Node(1)
root.left = Node(2); root.right = Node(3)
seen = {}
top_view(root, 0, seen)
for k in sorted(seen):
    print(seen[k], end=" ")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int seenVal[20], seenSet[20];
void topView(struct Node* n, int hd) {
    if (!n) return;
    if (!seenSet[hd+10]) { seenSet[hd+10] = 1; seenVal[hd+10] = n->val; }
    topView(n->left, hd - 1);
    topView(n->right, hd + 1);
}
int main() {
    struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
    struct Node root={1,&l,&r};
    topView(&root, 0);
    for (int i = 0; i < 20; i++) if (seenSet[i]) printf("%d ", seenVal[i]);
    return 0;
}

Bottom View

Bottom view top view का mirror है: हर horizontal distance पर पहला देखा गया node रखने के बजाय, यह आखिरी (bottommost) रखता है, क्योंकि नीचे वाले nodes visually उसी horizontal position पर ऊपर वालों को overwrite करते हैं।

उदाहरण: Bottom View

#include <iostream>
#include <map>
using namespace std;
struct Node { int val; Node *left, *right; };
void bottomView(Node* n, int hd, map<int,int>& seen) {
    if (!n) return;
    seen[hd] = n->val;
    bottomView(n->left, hd - 1, seen);
    bottomView(n->right, hd + 1, seen);
}
int main() {
    Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
    Node root={1,&l,&r};
    map<int,int> seen;
    bottomView(&root, 0, seen);
    for (auto& p : seen) cout << p.second << " ";
    return 0;
}
import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void bottomView(Node n, int hd, TreeMap<Integer,Integer> seen) {
        if (n == null) return;
        seen.put(hd, n.val);
        bottomView(n.left, hd - 1, seen);
        bottomView(n.right, hd + 1, seen);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2); root.right = new Node(3);
        TreeMap<Integer,Integer> seen = new TreeMap<>();
        bottomView(root, 0, seen);
        for (int v : seen.values()) System.out.print(v + " ");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def bottom_view(n, hd, seen):
    if n is None:
        return
    seen[hd] = n.val
    bottom_view(n.left, hd - 1, seen)
    bottom_view(n.right, hd + 1, seen)

root = Node(1)
root.left = Node(2); root.right = Node(3)
seen = {}
bottom_view(root, 0, seen)
for k in sorted(seen):
    print(seen[k], end=" ")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int seenVal[20], seenSet[20];
void bottomView(struct Node* n, int hd) {
    if (!n) return;
    seenSet[hd+10] = 1; seenVal[hd+10] = n->val;
    bottomView(n->left, hd - 1);
    bottomView(n->right, hd + 1);
}
int main() {
    struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
    struct Node root={1,&l,&r};
    bottomView(&root, 0);
    for (int i = 0; i < 20; i++) if (seenSet[i]) printf("%d ", seenVal[i]);
    return 0;
}

View Practice

सभी चार views सबसे naturally एक level-order (BFS) traversal से solve होते हैं, nodes process होते हुए या तो level number (left/right views के लिए) या root से horizontal distance (top/bottom views के लिए) track करते हुए।

उदाहरण: View Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Left/Right views use level-order BFS tracking level index; Top/Bottom views use DFS/BFS tracking horizontal distance" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Left/Right views use level-order BFS tracking level index; Top/Bottom views use DFS/BFS tracking horizontal distance");
    }
}
print("Left/Right views use level-order BFS tracking level index; Top/Bottom views use DFS/BFS tracking horizontal distance")
#include <stdio.h>
int main() {
    printf("Left/Right views use level-order BFS tracking level index; Top/Bottom views use DFS/BFS tracking horizontal distance\n");
    return 0;
}
Related Topics

Top Tree और Graph समस्याएँ · Top Array और String समस्याएँ · Top DP समस्याएँ · Tree को Serialize और Deserialize करना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक DFS उपयोग करना और left child पहले process किए बिना हर depth पर मिला पहला node लेना, इसलिए left view में गलत node दिखता है।
  2. Horizontal distance track करना भूल जाना, इसलिए top और bottom view अलग columns पर nodes mix up कर देते हैं।
  3. पहला रखने के बजाय top view entry को बाद के nodes से overwrite करना, जो bottom view देता है।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Lowest Common Ancestor Next Lesson → Serialize and Deserialize Tree

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.