मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इस ट्री को इनऑर्डर ट्रैवर्सल स्कीम का उपयोग करके बिना रिकर्सन के ट्रैवर्स करना है। इसलिए यदि ट्री इस तरह है
तब ट्रैवर्सल [2,5,7,10,15,20] होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- दो सरणी res और stack बनाएं, curr := root सेट करें
- एक अनंत लूप चलाएं
- जब तक current null नहीं है
- curr को स्टैक में पुश करें, और curr := curr का लेफ्ट सेट करें
- जब स्टैक की लंबाई = 0, तो res लौटाएं
- node := स्टैक से पॉप किया गया तत्व
- node के मान को res में डालें
- curr := curr का राइट सेट करें
- जब तक current null नहीं है
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data 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): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def inorderTraversal(self, root): res, stack = [], [] current = root while True: while current: stack.append(current) current = current.left if len(stack) == 0: return res node = stack[-1] stack.pop(len(stack)-1) if node.data != None: res.append(node.data) current = node.right return res ob1 = Solution() root = make_tree([10,5,15,2,7,None,20]) print(ob1.inorderTraversal(root))
इनपुट
[10,5,15,2,7,null,20]
आउटपुट
[2,5,7,10,15,20]
