Python trees are a lot like linked-list, but with a hierarchical order. Trees are composed of nodes that link to other nodes. The bottom node that doesn’t have a link are referred to as leaves. The node that linked to another node is known as the parent, and the linked-to are the children.
A tree is typically built with a wide range of nodes, or a cascading deep structure. So you can say a tree is either wide or deep.
An efficient version of a tree structure is known as the binary search tree. That’s where you only allow a parent node to have two children node. The node to the left is of a smaller value than the node to the right. Building a tree like this makes it very efficient to traverse, and find a particular value.
In the above example if I wanted to find the value of 98 from 39 I’d move right as 98 > 39 — from 70 move right again — from 97 move right, and in three moves I’ve found my desired node.
So let’s build a tree node in python, and see one in action. All we’ll need to initiate a tree node is a name. We’ll automatically assign it an empty list to hold all the children nodes to come.
If you’d read my earlier articles on python data structure this should look familiar.
Now as with any data structure we have to keep in mind the practical functionalities we’ll want our tree to have. Adding a node, and removing a node are obvious choices, and also easy to implement.
To add I’ll use the append() method, and to remove I’ll simply iterate through the self.children list, and re-add all the nodes with the exception of the node I want removed.
Next we’ll want to traverse the tree to find the information we want. To build this method we’ll start with an empty list to populate with each node to visit. While that node has children nodes we’ll pop it out, and add it to the list of nodes to visit.
Where do you think a data structure like this would be best utilized? Perhaps if we added some logic to access the nodes we could compartmentalize a lot of privileges a user could have.
Data trees are a great, and widely used tool in the coding world. I hope this brief introduction has at least given a worth while glimpse into why you’d want to know about these structures.