মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের একটি নোডের পয়েন্টার (নাম 'u') দেওয়া আছে এবং আমাদের সেই নোডের ঠিক ডানে অবস্থিত নোড বের করতে হবে। প্রদত্ত নোডের ডানে অবস্থিত নোড একই লেভেলে থাকতে হবে এবং দেওয়া নোড লিফ নোড বা ইন্টারন্যাল নোড হতে পারে।
যেমন, ইনপুট যদি এমন হয়:
এবং u = 6, তবে আউটপুট হবে 8।
নোড ৬-এর ডানে অবস্থিত নোড হল ৮, তাই মান ৮ রিটার্ন করা হবে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- যদি root খালি হয়, তবে null রিটার্ন করুন
- dq := একটি নতুন deque
- root dq-তে যোগ করুন
- dq খালি না হওয়া পর্যন্ত:
- dq_size := dq-এর আকার
- temp := একটি নতুন লিস্ট
- index := -1
- 0 থেকে dq_size পর্যন্ত প্রতিটি ভ্যালু জন্য:
- node := dq-এর শেষ এলিমেন্ট ডিলিট করুন
- যদি node.left খালি না হয়, তবে node.left dq-তে যোগ করুন
- যদি node.right খালি না হয়, তবে node.right dq-তে যোগ করুন
- node temp-এ যোগ করুন
- যদি node == u হয়, তবে index := temp-এর আকার - 1
- যদি index == temp-এর আকার - 1 হয়, তবে null রিটার্ন করুন
- যদি index > -1 হয়, তবে temp[index + 1] রিটার্ন করুন
- null রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
from queue import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if (root == None):
return None
if (root.val == element):
return root
res1 = search_node(root.left, element)
if res1:
return res1
res2 = search_node(root.right, element)
return res2
def solve(root, u):
if not root:
return None
dq = deque()
dq.append(root)
while dq:
dq_size = len(dq)
temp = []
index = -1
for _ in range(dq_size):
node = dq.pop()
if node.left:
dq.appendleft(node.left)
if node.right:
dq.appendleft(node.right)
temp.append(node)
if node == u:
index = len(temp) - 1
if index == len(temp) - 1:
return None
if index > -1:
return temp[index + 1]
return None
root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root,6)
ret = solve(root, u)
print(ret.val)
ইনপুট
root = make_tree([5, 3, 7, 2, 4, 6, 8]) u = search_node(root,6)
আউটপুট
8
