หาค่าสูงสุดใน Binary Tree ด้วย Inorder Traversal ใน Python

หาค่าสูงสุดใน Binary Tree โดยทำ Inorder Traversal (Left, Root, Right) และติดตามค่าสูงสุดที่เจอ

ตัวอย่างโค้ด

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
    
    def inorder_max(self):
        max_val = [float('-inf')]
        self._inorder_max_helper(max_val)
        return max_val[0]
    
    def _inorder_max_helper(self, max_val):
        if self.left:
            self.left._inorder_max_helper(max_val)
        if self.key > max_val[0]:
            max_val[0] = self.key
        if self.right:
            self.right._inorder_max_helper(max_val)

# Build tree
root = Node(8)
root.left = Node(9)
root.right = Node(4)

print("Max value:", root.inorder_max())

ผลลัพธ์

Max value: 9

คำอธิบาย

• ใช้ลิสต์ max_val = [-inf] เพื่อส่งผ่าน reference (mutable)

• Inorder: left → root → right

• อัปเดต max_val[0] ทุกโหนดที่เยี่ยมชม

• Tree: 8 (root), left=9, right=4 → max = 9

• หมายเหตุ: สำหรับ BST ค่าสูงสุดอยู่โหนดขวาสุดหาได้ O(h) เร็วกว่า