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

Binary Tree परिचय

एक binary tree एक family tree जैसा है जहां हर person के ज़्यादा से ज़्यादा दो children होते हैं, एक left और एक right।

In this page:

  1. Tree Basics
  2. Tree Node
  3. Tree Structure
  4. Leaf and Internal Nodes
  5. Binary Tree Practice
Syntax
markup 
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Tree Basics

एक binary tree एक hierarchical structure है जहां हर node के ज़्यादा से ज़्यादा दो children होते हैं, convention से left child और right child कहलाते हैं। यह binary search trees और heaps जैसी कई ज़्यादा specialized structures की नींव है जो इस basic shape के ऊपर extra rules जोड़ती हैं।

उदाहरण: Tree Basics

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node root = {1, nullptr, nullptr};
    cout << "Root value: " << root.val << ", left/right are null" << endl;
    return 0;
}
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);
        System.out.println("Root value: " + root.val + ", left/right are null");
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
print("Root value:", root.val, ", left/right are None")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node root = {1, NULL, NULL};
    printf("Root value: %d, left/right are null\n", root.val);
    return 0;
}

Tree Node

किसी binary tree में हर node आमतौर पर इसके children के लिए दो references (या pointers) के साथ एक value store करता है — उन references में से कोई भी null हो सकता है अगर वह child मौजूद न हो, जो यह है कि leaf nodes और single-child nodes कैसे represent किए जाते हैं।

उदाहरण: Tree Node

#include <iostream>
using namespace std;
struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
int main() {
    Node* n = new Node(5);
    cout << "Node value=" << n->val << " left=" << n->left << " right=" << n->right << endl;
    return 0;
}
public class Main {
    static class Node {
        int val; Node left, right;
        Node(int v) { val = v; left = null; right = null; }
    }
    public static void main(String[] args) {
        Node n = new Node(5);
        System.out.println("Node value=" + n.val + " left=" + n.left + " right=" + n.right);
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

n = Node(5)
print("Node value=", n.val, "left=", n.left, "right=", n.right)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node n = {5, NULL, NULL};
    printf("Node value=%d left=%p right=%p\n", n.val, (void*)n.left, (void*)n.right);
    return 0;
}

Tree Structure

पूरा tree एक single root node से शुरू होता है, हर दूसरा node इससे नीचे की ओर child links follow करके पहुंचने योग्य होते हुए — यह connectedness (cycles की absence के साथ) वह है जो एक tree को एक ज़्यादा general graph structure से अलग करता है।

उदाहरण: Tree Structure

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node c1 = {2, nullptr, nullptr};
    Node c2 = {3, nullptr, nullptr};
    Node root = {1, &c1, &c2};
    cout << "Reached child via root: " << root.left->val << ", " << root.right->val << endl;
    return 0;
}
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);
        System.out.println("Reached child via root: " + root.left.val + ", " + root.right.val);
    }
}
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)
print("Reached child via root:", root.left.val, ",", root.right.val)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
    struct Node root = {1, &c1, &c2};
    printf("Reached child via root: %d, %d\n", root.left->val, root.right->val);
    return 0;
}

Leaf and Internal Nodes

एक leaf node में बिल्कुल कोई children नहीं होती, tree की किसी branch के bottom पर बैठी होती है, जबकि एक internal node में कम से कम एक child होती है और root और leaves के बीच कहीं बैठती है।

उदाहरण: Leaf and Internal Nodes

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node leaf = {3, nullptr, nullptr};
    Node internal = {1, &leaf, nullptr};
    cout << (leaf.left == nullptr && leaf.right == nullptr ? "leaf is a leaf node" : "not a leaf") << endl;
    cout << (internal.left != nullptr ? "internal is an internal node" : "not internal") << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    public static void main(String[] args) {
        Node leaf = new Node(3);
        Node internal = new Node(1);
        internal.left = leaf;
        System.out.println(leaf.left == null && leaf.right == null ? "leaf is a leaf node" : "not a leaf");
        System.out.println(internal.left != null ? "internal is an internal node" : "not internal");
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

leaf = Node(3)
internal = Node(1)
internal.left = leaf
print("leaf is a leaf node" if leaf.left is None and leaf.right is None else "not a leaf")
print("internal is an internal node" if internal.left is not None else "not internal")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node leaf = {3, NULL, NULL};
    struct Node internal = {1, &leaf, NULL};
    printf("%s\n", (leaf.left == NULL && leaf.right == NULL) ? "leaf is a leaf node" : "not a leaf");
    printf("%s\n", internal.left != NULL ? "internal is an internal node" : "not internal");
    return 0;
}

Binary Tree Practice

Binary trees practice में recursively बनाए जाते हैं: एक tree या तो empty है, या यह एक left subtree और एक right subtree वाला एक node है, जिनमें से हर एक खुद एक छोटी binary tree है — यह recursive definition बिल्कुल कारण है कि recursive algorithms trees में इतनी naturally fit होते हैं।

उदाहरण: Binary Tree Practice

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int countNodes(Node* n) {
    if (n == nullptr) return 0;
    return 1 + countNodes(n->left) + countNodes(n->right);
}
int main() {
    Node c1 = {2, nullptr, nullptr}, c2 = {3, nullptr, nullptr};
    Node root = {1, &c1, &c2};
    cout << "Total nodes: " << countNodes(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int countNodes(Node n) {
        if (n == null) return 0;
        return 1 + countNodes(n.left) + countNodes(n.right);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        System.out.println("Total nodes: " + countNodes(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def count_nodes(n):
    if n is None:
        return 0
    return 1 + count_nodes(n.left) + count_nodes(n.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Total nodes:", count_nodes(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int countNodes(struct Node* n) {
    if (n == NULL) return 0;
    return 1 + countNodes(n->left) + countNodes(n->right);
}
int main() {
    struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
    struct Node root = {1, &c1, &c2};
    printf("Total nodes: %d\n", countNodes(&root));
    return 0;
}
Related Topics

Binary Search Tree क्या है · Answer पर Binary Search · Binary Search क्या है · Tree Traversals यानि Inorder, Preorder, Postorder

{# 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. nullptr जांचे बिना node->left->val पढ़ना, जो leaves पर crash करता है।
  2. एक struct में left और right को uninitialized छोड़ना, इसलिए वे nullptr के बजाय garbage रखते हैं।
  3. एक binary tree (ज़्यादा से ज़्यादा दो children) को एक binary search tree के साथ confuse करना, जिसे एक ordering rule भी चाहिए।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Jump Search Next Lesson → Tree Traversals Inorder Preorder Postorder

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.