ভূমিকা
Tree হলো computer science-এর সবচেয়ে গুরুত্বপূর্ণ data structure গুলোর একটি। Binary Tree, Binary Search Tree (BST), এবং তাদের বিভিন্ন operations interview-এ খুব বেশি আসে। Tree-এর সমস্যাগুলো সাধারণত recursion এবং DFS/BFS দিয়ে সমাধান করা হয়। এই পোস্টে আমরা Tree-এর ৫টি medium-level সমস্যা ও সমাধান দেখব।
সমস্যা ১: Binary Tree Maximum Path Sum
সমস্যার বিবরণ
একটি binary tree দেওয়া আছে। Tree-এর যেকোনো node থেকে যেকোনো node পর্যন্ত path-এর maximum sum বের করতে হবে। Path-এ একটি node একবারের বেশি আসতে পারবে না।
উদাহরণ
Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
কারণ: 15 → 20 → 7 = 42 (maximum path sum)
Input: root = [1, 2, 3]
Output: 6
কারণ: 2 → 1 → 3 = 6
চিন্তার পদ্ধতি
প্রতিটি node-এ দুটি জিনিস track করতে হবে। প্রথমত, global maximum path sum (যেকোনো দুটি node-এর মধ্যে)। দ্বিতীয়ত, সেই node থেকে নিচের দিকে maximum gain (parent-এর জন্য)। DFS-এ প্রতিটি node-এ left ও right subtree-এর max gain হিসাব করব এবং current node দিয়ে path sum update করব।
সমাধান (Java)
public class BinaryTreeMaxPathSum {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
private int maxSum = Integer.MIN_VALUE; // Global maximum
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
// Left ও right subtree থেকে maximum gain (negative হলে 0 নিই)
int leftGain = Math.max(dfs(node.left), 0);
int rightGain = Math.max(dfs(node.right), 0);
// Current node দিয়ে path sum (left + node + right)
int currentPathSum = node.val + leftGain + rightGain;
// Global maximum update করি
maxSum = Math.max(maxSum, currentPathSum);
// Parent-এর জন্য maximum gain return করি (একদিক বেছে নিই)
return node.val + Math.max(leftGain, rightGain);
}
public static void main(String[] args) {
BinaryTreeMaxPathSum solution = new BinaryTreeMaxPathSum();
// Tree: -10 → [9, 20 → [15, 7]]
TreeNode root = new TreeNode(-10);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(solution.maxPathSum(root)); // Output: 42
BinaryTreeMaxPathSum solution2 = new BinaryTreeMaxPathSum();
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(2);
root2.right = new TreeNode(3);
System.out.println(solution2.maxPathSum(root2)); // Output: 6
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(h) যেখানে h = tree height
সমস্যা ২: Validate Binary Search Tree
সমস্যার বিবরণ
একটি binary tree দেওয়া আছে। এটি valid Binary Search Tree (BST) কিনা তা নির্ধারণ করতে হবে। BST-এর শর্ত: left subtree-এর সব node current node-এর চেয়ে ছোট এবং right subtree-এর সব node current node-এর চেয়ে বড়।
উদাহরণ
Input: root = [2, 1, 3]
Output: true
Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
কারণ: root হলো 5 কিন্তু right child 4 যা 5-এর চেয়ে ছোট
চিন্তার পদ্ধতি
শুধু child-এর সাথে parent তুলনা করলে ভুল হবে। প্রতিটি node-এর জন্য একটি valid range (min, max) রাখতে হবে। Left-এ গেলে max = current node value, Right-এ গেলে min = current node value।
সমাধান (Java)
public class ValidateBST {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true; // Null node সবসময় valid
// Current node value range-এর মধ্যে আছে কিনা চেক করি
if (node.val <= min || node.val >= max) return false;
// Left subtree: max = current value
// Right subtree: min = current value
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
public static void main(String[] args) {
ValidateBST solution = new ValidateBST();
// Valid BST: 2 → [1, 3]
TreeNode root1 = new TreeNode(2);
root1.left = new TreeNode(1);
root1.right = new TreeNode(3);
System.out.println(solution.isValidBST(root1)); // Output: true
// Invalid BST: 5 → [1, 4 → [3, 6]]
TreeNode root2 = new TreeNode(5);
root2.left = new TreeNode(1);
root2.right = new TreeNode(4);
root2.right.left = new TreeNode(3);
root2.right.right = new TreeNode(6);
System.out.println(solution.isValidBST(root2)); // Output: false
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(h) যেখানে h = tree height
সমস্যা ৩: Lowest Common Ancestor (LCA) of a Binary Tree
সমস্যার বিবরণ
একটি binary tree এবং দুটি node p ও q দেওয়া আছে। এদের Lowest Common Ancestor (LCA) বের করতে হবে। LCA হলো সেই node যেটি p এবং q উভয়ের ancestor এবং root থেকে সবচেয়ে দূরে।
উদাহরণ
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
কারণ: 5 এবং 1 উভয়ের LCA হলো 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
কারণ: 4 হলো 5-এর subtree-এ, তাই LCA হলো 5 নিজেই
চিন্তার পদ্ধতি
DFS ব্যবহার করব। যদি current node null হয় অথবা p বা q-এর সমান হয় তাহলে সেটি return করব। Left ও right subtree-তে recursively খুঁজব। যদি উভয় side-এ কিছু পাওয়া যায় তাহলে current node হলো LCA। যদি একদিকে পাওয়া যায় তাহলে সেই দিক return করব।
সমাধান (Java)
public class LowestCommonAncestor {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base case: null অথবা p বা q পেলে return করি
if (root == null || root == p || root == q) return root;
// Left ও right subtree-এ খুঁজি
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// উভয় side-এ পাওয়া গেলে current node হলো LCA
if (left != null && right != null) return root;
// একদিকে পাওয়া গেলে সেটি return করি
return left != null ? left : right;
}
public static void main(String[] args) {
LowestCommonAncestor solution = new LowestCommonAncestor();
TreeNode root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
TreeNode p = root.left; // Node 5
TreeNode q = root.right; // Node 1
System.out.println(solution.lowestCommonAncestor(root, p, q).val); // Output: 3
TreeNode p2 = root.left; // Node 5
TreeNode q2 = root.left.right.right; // Node 4
System.out.println(solution.lowestCommonAncestor(root, p2, q2).val); // Output: 5
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(h) যেখানে h = tree height
সমস্যা ৪: Construct Binary Tree from Preorder and Inorder Traversal
সমস্যার বিবরণ
একটি binary tree-এর preorder এবং inorder traversal দেওয়া আছে। এই দুটো traversal থেকে original binary tree reconstruct করতে হবে।
উদাহরণ
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
কারণ:
3
/ \
9 20
/ \
15 7
চিন্তার পদ্ধতি
Preorder-এর প্রথম element সবসময় root। Inorder-এ root খুঁজে পেলে বাম দিক left subtree এবং ডান দিক right subtree। HashMap দিয়ে inorder index O(1)-এ খুঁজব। Recursively left ও right subtree build করব।
সমাধান (Java)
import java.util.*;
public class BuildTreeFromTraversal {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
private Map<Integer, Integer> inorderMap = new HashMap<>();
private int preorderIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// Inorder value → index HashMap তৈরি করি
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int left, int right) {
if (left > right) return null; // Base case
// Preorder থেকে root নিই
int rootVal = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootVal);
// Inorder-এ root-এর position খুঁজি
int mid = inorderMap.get(rootVal);
// Left subtree: inorder[left...mid-1]
root.left = build(preorder, left, mid - 1);
// Right subtree: inorder[mid+1...right]
root.right = build(preorder, mid + 1, right);
return root;
}
// Inorder traversal দিয়ে verify করি
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) return;
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
public static void main(String[] args) {
BuildTreeFromTraversal solution = new BuildTreeFromTraversal();
int[] preorder = {3, 9, 20, 15, 7};
int[] inorder = {9, 3, 15, 20, 7};
TreeNode root = solution.buildTree(preorder, inorder);
List<Integer> result = new ArrayList<>();
solution.inorder(root, result);
System.out.println(result); // Output: [9, 3, 15, 20, 7]
System.out.println("Root: " + root.val); // Output: Root: 3
System.out.println("Left: " + root.left.val); // Output: Left: 9
System.out.println("Right: " + root.right.val); // Output: Right: 20
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)
সমস্যা ৫: Kth Smallest Element in a BST
সমস্যার বিবরণ
একটি Binary Search Tree (BST) এবং একটি integer k দেওয়া আছে। BST-এর k-তম smallest element বের করতে হবে।
উদাহরণ
Input: root = [3,1,4,null,2], k = 1
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
চিন্তার পদ্ধতি
BST-এর inorder traversal (left → root → right) সবসময় sorted order-এ elements দেয়। তাই inorder traversal করতে করতে k-তম element পেলেই সেটি return করব। Iterative approach stack দিয়ে করলে early termination সম্ভব।
সমাধান (Java)
import java.util.*;
public class KthSmallestInBST {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
int count = 0;
while (current != null || !stack.isEmpty()) {
// সবচেয়ে বাম node পর্যন্ত যাই
while (current != null) {
stack.push(current);
current = current.left;
}
// Node process করি
current = stack.pop();
count++;
if (count == k) return current.val; // k-তম smallest পেলাম
// Right subtree-এ যাই
current = current.right;
}
return -1; // k valid না হলে
}
public static void main(String[] args) {
KthSmallestInBST solution = new KthSmallestInBST();
// BST: 3 → [1 → [null, 2], 4]
TreeNode root1 = new TreeNode(3);
root1.left = new TreeNode(1);
root1.right = new TreeNode(4);
root1.left.right = new TreeNode(2);
System.out.println(solution.kthSmallest(root1, 1)); // Output: 1
System.out.println(solution.kthSmallest(root1, 2)); // Output: 2
System.out.println(solution.kthSmallest(root1, 3)); // Output: 3
// BST: 5 → [3 → [2 → [1], 4], 6]
TreeNode root2 = new TreeNode(5);
root2.left = new TreeNode(3);
root2.right = new TreeNode(6);
root2.left.left = new TreeNode(2);
root2.left.right = new TreeNode(4);
root2.left.left.left = new TreeNode(1);
System.out.println(solution.kthSmallest(root2, 3)); // Output: 3
}
}
সময় জটিলতা: O(h + k) | স্থান জটিলতা: O(h) যেখানে h = tree height
সারসংক্ষেপ
| সমস্যা | পদ্ধতি | Data Structure | সময় জটিলতা | স্থান জটিলতা |
|---|---|---|---|---|
| Binary Tree Maximum Path Sum | DFS (Post-order) | Recursion Stack | O(n) | O(h) |
| Validate BST | DFS + Range Check | Recursion Stack | O(n) | O(h) |
| Lowest Common Ancestor | DFS (Post-order) | Recursion Stack | O(n) | O(h) |
| Build Tree from Traversals | DFS + HashMap | HashMap + Recursion | O(n) | O(n) |
| Kth Smallest in BST | Inorder Traversal | Stack | O(h + k) | O(h) |
Tree সমস্যার মূল কৌশল: বেশিরভাগ Tree সমস্যা DFS (recursion) দিয়ে সমাধান করা যায়। Base case হিসেবে null node handle করুন। Preorder ব্যবহার করুন top-down তথ্য পাঠাতে, Postorder ব্যবহার করুন bottom-up ফলাফল সংগ্রহ করতে। BST-এর ক্ষেত্রে inorder traversal সবসময় sorted result দেয় — এটি একটি শক্তিশালী property।