Python BST 바이너리 서치 트리 Traversal + Height

class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def traverse(tree, arr=[]):
    if tree is not None:
        #inOrder arr.append(tree.value)
        traverse(tree.left, arr)
        #preOrder arr.append(tree.value)
        traverse(tree.right, arr)
        #postOrder arr.append(tree.value)
    return arr

 

EX) 아래 그래프는

# 그래프 생성
root = BST(10)

root.left = BST(5)
root.left.left = BST(2)
root.left.left.left = BST(1)
root.left.right = BST(5)

root.right = BST(15)
root.right.right = BST(25)

inOrder = [1, 2, 5, 5, 10, 15, 22]

preOrder = [10, 5, 2, 1, 5, 15, 22]

postOrder = [1, 2, 5, 5, 22, 15, 10]

 

아래는 Max Height를 구하는 방법이다.

def getTreeHeight(tree, height=0):
    if tree is None:
        return height
    leftTreeHeight = getTreeHeight(tree.left, height + 1)
    rightTreeHeight = getTreeHeight(tree.right, height + 1)
    return max(leftTreeHeight, rightTreeHeight)