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

Tree की Height और Diameter

Height यह है कि tree के top से एक leaf तक सबसे लंबा path कितने steps लेता है, और diameter किन्हीं भी दो leaves के बीच सबसे लंबा path है, tree के सबसे चौड़े हिस्से में measure करने जैसा।

In this page:

  1. Tree Height
  2. Recursive Height
  3. Tree Diameter
  4. Height and Diameter Together
  5. Practice
Syntax
markup 
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

Tree Height

किसी tree की height root से नीचे किसी भी leaf तक सबसे लंबे path की length है, आमतौर पर चुने convention के आधार पर edges या levels की संख्या में measured — यह course इसे node levels में count करता है।

उदाहरण: Tree Height

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Height in levels: 2 (root -> leaf), or 1 edge from root to leaf" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf");
    }
}
print("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf")
#include <stdio.h>
int main() {
    printf("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf\n");
    return 0;
}

Recursive Height

Height recursively compute होती है: किसी node की height एक plus इसकी left और right subtree की heights में से बड़ी है, recursive base case के रूप में एक empty subtree zero (या convention के आधार पर negative one) की height contribute करते हुए।

उदाहरण: Recursive Height

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Height: " << height(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Height: " + height(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Height:", height(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Height: %d\n", height(&root));
    return 0;
}

Tree Diameter

किसी tree का diameter tree में किन्हीं भी दो nodes के बीच सबसे लंबे path की length है, जो root से होकर गुज़र सकता है या नहीं भी — यह diameter को height से ज़्यादा tricky बनाता है, क्योंकि सबसे लंबा path पूरी तरह एक subtree के अंदर हो सकता है।

उदाहरण: Tree Diameter

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int diameter(Node* n) {
    if (!n) return 0;
    int through = height(n->left) + height(n->right);
    int left = diameter(n->left), right = diameter(n->right);
    int best = through > left ? through : left;
    return best > right ? best : right;
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Diameter: " << diameter(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) { if(n==null) return 0; return 1+Math.max(height(n.left),height(n.right)); }
    static int diameter(Node n) {
        if (n == null) return 0;
        int through = height(n.left) + height(n.right);
        return Math.max(through, Math.max(diameter(n.left), diameter(n.right)));
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Diameter: " + diameter(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None: return 0
    return 1 + max(height(n.left), height(n.right))

def diameter(n):
    if n is None:
        return 0
    through = height(n.left) + height(n.right)
    return max(through, diameter(n.left), diameter(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Diameter:", diameter(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int diameter(struct Node* n) {
    if (!n) return 0;
    int through = height(n->left) + height(n->right);
    int left = diameter(n->left), right = diameter(n->right);
    int best = through > left ? through : left;
    return best > right ? best : right;
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Diameter: %d\n", diameter(&root));
    return 0;
}

Height and Diameter Together

Diameter और height एक single traversal में एक साथ compute किए जा सकते हैं: हर node की height recursively compute करते समय, यह भी जांचें कि क्या उस node के through path (left height plus right height) अब तक देखी best diameter को हराता है।

उदाहरण: Height and Diameter Together

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int best = 0;
int heightAndDiameter(Node* n) {
    if (!n) return 0;
    int l = heightAndDiameter(n->left), r = heightAndDiameter(n->right);
    if (l + r > best) best = l + r;
    return 1 + (l > r ? l : r);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    int h = heightAndDiameter(&root);
    cout << "Height: " << h << ", Diameter (computed in same pass): " << best << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int best = 0;
    static int heightAndDiameter(Node n) {
        if (n == null) return 0;
        int l = heightAndDiameter(n.left), r = heightAndDiameter(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        int h = heightAndDiameter(root);
        System.out.println("Height: " + h + ", Diameter (computed in same pass): " + best);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

best = 0
def height_and_diameter(n):
    global best
    if n is None:
        return 0
    l = height_and_diameter(n.left)
    r = height_and_diameter(n.right)
    best = max(best, l + r)
    return 1 + max(l, r)

root = Node(5)
root.left = Node(3); root.right = Node(8)
h = height_and_diameter(root)
print("Height:", h, ", Diameter (computed in same pass):", best)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int best = 0;
int heightAndDiameter(struct Node* n) {
    if (!n) return 0;
    int l = heightAndDiameter(n->left), r = heightAndDiameter(n->right);
    if (l + r > best) best = l + r;
    return 1 + (l > r ? l : r);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    int h = heightAndDiameter(&root);
    printf("Height: %d, Diameter (computed in same pass): %d\n", h, best);
    return 0;
}

Practice

Height और diameter problems tree recursion exercise की एक आम category हैं क्योंकि उन्हें एक straightforward recursive computation (height) को पूरी traversal में एक running best value (diameter) track करने के साथ combine करना चाहिए।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step");
    }
}
print("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step")
#include <stdio.h>
int main() {
    printf("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step\n");
    return 0;
}
Related Topics

AVL Tree क्या है · Tree Views यानि Left, Right, Top, Bottom · Binary Search Tree क्या है · 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. Nodes count करने और edges count करने को mix up करना, इसलिए एक single node एक जगह height 1 और दूसरी जगह 0 है।
  2. यह भूल जाना कि diameter root से नहीं गुज़र सकता, इसलिए सिर्फ root पर height(left) + height(right) जांचा जाता है।
  3. Diameter loop के अंदर हर node पर height recompute करना, जो इसे O(n^2) बनाता है।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson AVL Tree Next Lesson → Lowest Common Ancestor

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.