একটি বাইনারি ট্রি একটি শ্রেণিবদ্ধ কাঠামো যেখানে প্রতিটি নোড-এর সর্বাধিক দুটি সন্তান থাকে, যাদের নাম left এবং । এটির একটি একক রয়েছে; সন্তান ছাড়া নোডগুলি । এটি BST, হিপ এবং অভিব্যক্তি গাছের ভিত্তি।
একটি বাইনারি ট্রি একটি শ্রেণিবদ্ধ কাঠামো যেখানে প্রতিটি নোড-এর সর্বাধিক দুটি সন্তান থাকে, যাদের নাম left এবং । এটির একটি একক রয়েছে; সন্তান ছাড়া নোডগুলি । এটি BST, হিপ এবং অভিব্যক্তি গাছের ভিত্তি।
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)
একটি স্তর-ক্রম (BFS) ট্রাভার্সাল একটি কিউ ব্যবহার করে এবং গভীরতা অনুযায়ী পরিদর্শন করে।
| Traversal | Order | Common use |
|---|---|---|
| Inorder | L, N, R | sorted output of a BST |
| Preorder | N, L, R | copy/serialize a tree |
| Postorder | L, R, N | delete a tree, evaluate expr |
| Level-order | by depth | BFS, shortest path on tree |
প্রতিটি ট্রাভার্সাল প্রতিটি নোড একবার পরিদর্শন করে → O(n) সময়, O(h) স্ট্যাক স্পেস যেখানে h হল উচ্চতা।
বাইনারি ট্রি প্রাকৃতিকভাবে শ্রেণিবদ্ধ ডেটা (ফাইল সিস্টেম, পার্স ট্রি, সিদ্ধান্ত গাছ) মডেল করে এবং দক্ষ অনুসন্ধান এবং সাজানোর কাঠামোর ভিত্তি।
চারটি ট্রাভার্সালে দক্ষতা প্রয়োজনীয় — বেশিরভাগ ট্রি ইন্টারভিউ প্রশ্ন এর একটি বৈচিত্র।