একটি বাইনারি ট্রি দেওয়া থাকলে, এর বাম পাশের নোডগুলো (Left View) প্রিন্ট করতে হবে।
প্রতিটি নোডের অধিকতম ২টি চাইল্ড থাকে। এই সমস্যায় শুধু লেফট পয়েন্টার ট্রাভার্স করলেই চলে।
যদি লেফট পয়েন্টার NULL না হয়, তবে সেটি আরো নিচে যাবে। NULL হলে সেটি লেফট চাইল্ড হিসেবে প্রিন্ট হবে।
উদাহরণ
Input: 1 0 3 2 4 Output: 1 0 2
নারাঞ্জি রঙের নোডগুলো লেফট ভিউ। রুট নোড ১ প্রিন্ট হবে, তারপর লেফট চাইল্ড ০, তারপর ৩-এর লেফট চাইল্ড ২।
রিকার্সিভ পদ্ধতিতে নোডের লেভেল স্টোর করে রাইট সাবট্রিও ট্রাভার্স করা হয়।
অ্যালগরিদম
START
Step 1: Create node structure with data, left, right
Step 2: Function New(int data) to create node
Step 3: Function left_view(node* root, int level, int* highest_level)
IF root == NULL RETURN
IF *highest_level < level
PRINT root->data
*highest_level = level
CALL left_view(root->left, level+1, highest_level)
CALL left_view(root->right, level+1, highest_level)
Step 4: Function left(node* root)
highest_level = 0
CALL left_view(root, 1, &highest_level)
Step 5: In main()
Create tree, call left(root)
STOP
সি প্রোগ্রাম
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* New(int new_data) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = new_data;
temp->left = temp->right = NULL;
return temp;
}
void left_view(struct node* root, int level, int* highest_level) {
if (root == NULL) return;
if (*highest_level < level) {
printf("%d\t", root->data);
*highest_level = level;
}
left_view(root->left, level + 1, highest_level);
left_view(root->right, level + 1, highest_level);
}
void left(struct node* root) {
int highest_level = 0;
left_view(root, 1, &highest_level);
}
int main() {
printf("left view of a binary tree is: ");
struct node* root = New(1);
root->left = New(0);
root->right = New(3);
root->right->left = New(2);
root->right->right = New(4);
left(root);
return 0;
}
আউটপুট
left view of a binary tree is: 1 0 2
