ایک binary tree ایک درجہ بندی والا ڈھانچہ ہے جہاں ہر node کے زیادہ سے زیادہ دو بچے ہوتے ہیں، جنہیں left اور کہا جاتا ہے۔ اس کا ایک واحد ہے؛ جن nodes کے کوئی بچے نہیں ہوتے وہ ہیں۔ یہ BSTs، heaps، اور expression trees کی بنیاد ہے۔
ایک binary tree ایک درجہ بندی والا ڈھانچہ ہے جہاں ہر node کے زیادہ سے زیادہ دو بچے ہوتے ہیں، جنہیں left اور کہا جاتا ہے۔ اس کا ایک واحد ہے؛ جن 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 | عام استعمال |
|---|---|---|
| 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 |
ہر traversal ہر node کو ایک بار دیکھتا ہے → O(n) وقت، O(h) stack space جہاں h ہے height۔
بائنری ٹریز قدرتی طور پر درجہ بندی والے ڈیٹا کو ماڈل کرتے ہیں (file systems، parse trees، decision trees) اور موثر تلاش اور sorting کے ڈھانچوں کی بنیاد ہیں۔
چاروں traversals میں مہارت حاصل کرنا ضروری ہے — زیادہ تر tree interview کے مسائل ان میں سے کسی ایک کی تبدیلی ہوتے ہیں۔