পাইথনে বাইনারি ট্রি প্রি-অর্ডার ট্রাভার্সাল

ধরুন একটি বাইনারি ট্রি আছে। আমাদের সেই ট্রির প্রি-অর্ডার ট্রাভার্সাল রিটার্ন করতে হবে। যদি ট্রি নিচের মতো হয়:

তবে প্রি-অর্ডার ট্রাভার্সাল হবে: [3,9,20,15,7]

সমাধানের ধাপসমূহ:

• res এবং st নামক দুটি খালি লিস্ট তৈরি
• node := root
• while node বা st খালি নয়
  • while node is not null
    • node-এর val res-এ ইনসার্ট, node st-এ ইনসার্ট, node := node-এর left
  • temp := st-এর শেষ এলিমেন্ট, st-এর শেষ এলিমেন্ট ডিলিট
  • যদি temp-এর right থাকে
    • node := temp-এর right
• return res

উদাহরণ

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 preorderTraversal(self, root):
        res = []
        st = []
        node = root
        while node or st:
            while node:
                if node.data != None:
                    res.append(node.data)
                    st.append(node)
                node = node.left
            temp = st[-1]
            st.pop()
            if temp.right:
                node = temp.right
        return res

ob1 = Solution()
head = make_tree([3,9,20,None,None,15,7])
print(ob1.preorderTraversal(head))

ইনপুট

[3,9,20,null,null,15,7]

আউটপুট

[3, 9, 20, 15, 7]