Menghitung Height dari Binary Search Tree

Yang dimaksud dengan height dari binary search tree adalah berapa banyak node dari root sampai ke leaf terdalam. Leaf adalah node yang tidak memiliki children.

Pada gambar dibawah, maka dapat dihitung, tinggi dari binary search tree adalah 4.

Ide dari cara perhitungan height adalah kunjungi semua node, dimulai dari root, dan lakukan perhitungan tinggi, setiap kali perhitungan tinggi dilakukan, increment nilai height.

Pertama kali Inisialisasi nilai height adalah 0, yaitu pada root. Jika child node ada, maka increment height dengan nilai 1, jika tidak height adalah nilai height sebelumnya.

Lakukan untuk node kiri dan kanan. Lalu return dengan fungsi max, untuk mendapatkan nilai height tertinggi.

Berikut code perhitungan height

def height(self, h=0):
    leftHeight = self.left.height(h+1) if self.left else h
    rightHeight = self.right.height(h+1) if self.right else h
    return max(leftHeight, rightHeight)

Tambahkan juga fungsi height pada class Tree

def height(self):
    return self.root.height()

Berikut code lengkap dari program binary search tree.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def search(self, target):
        if self.data == target:
            print("Node found")
            return self
        
        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("No Node Found")

    def traversePreorder(self):
        print(self.data)
        if self.left:
            self.left.traversePreorder()
        
        if self.right:
            self.right.traversePreorder()

    def traverseInorder(self):
        if self.left:
            self.left.traverseInorder()
        print(self.data)
        if self.right:
            self.right.traverseInorder()

    def traversePostorder(self):
        if self.left:
            self.left.traversePostorder()
        
        if self.right:
            self.right.traversePostorder()
        
        print(self.data)

    def height(self, h=0):
        leftHeight = self.left.height(h+1) if self.left else h
        rightHeight = self.right.height(h+1) if self.right else h
        return max(leftHeight, rightHeight)



class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)

    def traversePreorder(self):
        self.root.traversePreorder()

    def traverseInorder(self):
        self.root.traverseInorder()

    def traversePostorder(self):
        self.root.traversePostorder()

    def height(self):
        return self.root.height()


node = Node(55)

node.left = Node(25)
node.right = Node(70)

node.left.left = Node(15)
node.left.right = Node(35)

node.right.right = Node(75)

node.left.left.left = Node(5)
node.left.left.right = Node(20)

node.left.left.left.left = Node(1)

myTree = Tree(node, 'Basic BST')

print(myTree.height())

$ python tree.py
4

Jika kita jalankan program diatas, sesuai dengan ekspetasi, tinggi tree adalah 4.