Oct-01-2019, 04:57 PM
This is a standard binary tree. Basically, it's a linked list combined with a sorting algorithm.
When inserting a value, insert() determines the current state of the node and evaluates how the new value compares. If the value is None, it creates a node. If the new value is lower, it recurses and evaluates the left child node of the current node and repeats the process. Likewise, if the value is higher, it does the same process to the right child node.
The end result is a data structure of nodes that know about other nodes, their children. Plus, they're all sorted by value. When you use inorder() on this data structure, it asks a question: Who are your children and where do they live? Then, it asks the left child the same question until there are no more children. It prints the value of the last child, then that child's parent, and then it asks the same question to the right child.
Geeks for Geeks has a great series on binary trees and different variants. They have gifs to demonstrate them too.
When inserting a value, insert() determines the current state of the node and evaluates how the new value compares. If the value is None, it creates a node. If the new value is lower, it recurses and evaluates the left child node of the current node and repeats the process. Likewise, if the value is higher, it does the same process to the right child node.
The end result is a data structure of nodes that know about other nodes, their children. Plus, they're all sorted by value. When you use inorder() on this data structure, it asks a question: Who are your children and where do they live? Then, it asks the left child the same question until there are no more children. It prints the value of the last child, then that child's parent, and then it asks the same question to the right child.
Geeks for Geeks has a great series on binary trees and different variants. They have gifs to demonstrate them too.