ইনঅর্ডার ট্রাভার্সাল (LNR)
বাইনারি ট্রি-এ ইনঅর্ডার ট্রাভার্সাল মানে: বাম সাবট্রি → রুট → ডান সাবট্রি। এটি বাইনারি সার্চ ট্রিতে সোর্টেড আউটপুট দেয়। রিকার্শন না ব্যবহার করে স্ট্যাক (Stack) দিয়ে ইটারেটিভলি করা যায়।
অ্যালগরিদম
Function inOrder(root):
stack s
current = root
while (current != NULL OR !s.empty()):
while (current != NULL):
s.push(current)
current = current->left
current = s.top(); s.pop()
print current->data
current = current->rightউদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int d) : data(d), left(NULL), right(NULL) {}
};
void inOrder(Node *root) {
stack<Node*> s;
Node *curr = root;
while (curr != NULL || !s.empty()) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;
}
curr = s.top(); s.pop();
cout << curr->data << " ";
curr = curr->right;
}
}
int main() {
Node *root = new Node(7);
root->left = new Node(6);
root->right = new Node(2);
root->left->left = new Node(1);
root->left->right = new Node(9);
inOrder(root); // আউটপুট: 1 6 9 7 2
return 0;
}আউটপুট
1 6 9 7 2
সময় জটিলতা: O(n), স্পেস জটিলতা: O(h) (h = ট্রির উচ্চতা)।
