[PYTHON] Binary tree traverse is difficult to understand

binary tree When you see the wiki link below https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8#:~:text=%E4%BA%8C%E5%88%86%E6%9C%A8%EF%BC%88binary%20tree%3B%20%E4%BA%8C,%E3%81%A7%E3%81%82%E3%82%8B%E3%82%82%E3%81%AE%E3%82%92%E3%81%84%E3%81%86%E3%80%82

・ Root: Top point = ② ・ Node: Points = All points from ② to 11 ・ Link: Connecting lines = All lines connecting ② to 11 Is pointing to.

About traverse

#About the following functions(Postorder)
#getLeftChild=Move to the point on the left
#getRightChild=Move to the point on the right
#getRootVal = move to the top point
#In other words, in the following cases, take the right, take the left, and then take the center.
#In the wiki, 2-5-11-6-7-4-9-5-2
def traverse(tree):
    if tree:
        traverse(tree.getLeftChild())
        traverse(tree.getRightChild())
        print(tree.getRootVal())

About sorted BST The average runtime is O (logn) The worst runtime is O (n) The worst case is when all child nodes have only one

In BST, the left must always be small and the right must be large.