एक बायनरी ट्री एक श्रेणीबद्ध संरचना आहे जिथे प्रत्येक नोड मध्ये जास्तीत जास्त दोन संतान असतात, ज्यांना left आणि म्हणतात. यात एकच असतो; कोणतीही संतान नसलेल्या नोड्सना म्हणतात. हे BST, heaps आणि expression trees चा आधार आहे.
एक बायनरी ट्री एक श्रेणीबद्ध संरचना आहे जिथे प्रत्येक नोड मध्ये जास्तीत जास्त दोन संतान असतात, ज्यांना left आणि म्हणतात. यात एकच असतो; कोणतीही संतान नसलेल्या नोड्सना म्हणतात. हे BST, 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) ट्रॅव्हर्सल एक queue वापरते आणि depth नुसार भेट देते.
| ट्रॅव्हर्सल | ऑर्डर | सामान्य उपयोग |
|---|---|---|
| Inorder | L, N, R | BST चे sorted output |
| Preorder | N, L, R | tree copy/serialize |
| Postorder | L, R, N | tree delete, expr evaluate |
| Level-order | by depth | BFS, tree वर shortest path |
प्रत्येक ट्रॅव्हर्सल प्रत्येक नोड ला एक वेळ भेट देते → O(n) वेळ, O(h) stack space जिथे h हा height आहे.
बायनरी ट्रीज नैसर्गिकरित्या श्रेणीबद्ध डेटा (file systems, parse trees, decision trees) मॉडेल करतात आणि कार्यक्षम search आणि sorting structures ला आधार देतात.
चार ट्रॅव्हर्सल्स मास्टर करणे आवश्यक आहे — बहुतेक tree interview समस्या यातील एकाचा variation आहेत.