एक binary tree एक श्रेणीबद्ध संरचना है जहाँ प्रत्येक node के अधिकतम दो children होते हैं, जिन्हें left और कहते हैं। इसका एक ही होता है; बिना children वाले nodes कहलाते हैं। यह BSTs, heaps और expression trees का आधार है।
एक binary tree एक श्रेणीबद्ध संरचना है जहाँ प्रत्येक node के अधिकतम दो children होते हैं, जिन्हें left और कहते हैं। इसका एक ही होता है; बिना children वाले nodes कहलाते हैं। यह BSTs, heaps और expression trees का आधार है।
right 1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
एक level-order (BFS) traversal एक queue का उपयोग करता है और गहराई दर गहराई देखता है।
| Traversal | Order | Common use |
|---|---|---|
| Inorder | L, N, R | BST का sorted output |
| Preorder | N, L, R | tree को copy/serialize करना |
| Postorder | L, R, N | tree हटाना, expr का मूल्यांकन |
| Level-order | by depth | BFS, tree पर shortest path |
प्रत्येक traversal हर node को एक बार देखता है → O(n) time, O(h) stack space जहाँ h ऊँचाई है।
Binary trees स्वाभाविक रूप से श्रेणीबद्ध data (file systems, parse trees, decision trees) को मॉडल करते हैं और कुशल search तथा sorting संरचनाओं को आधार प्रदान करते हैं।
चारों traversals में महारत आवश्यक है — अधिकांश tree interview समस्याएँ इनमें से किसी एक का रूपांतर होती हैं।