Python Trees

Python Trees: An Introduction

A Tree is a widely used non-linear data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent-child relationship. Unlike arrays or linked lists, which are linear, trees can have multiple branches.

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node.

Key Terminology

Understanding the vocabulary is the first step to mastering trees.

• Node: The fundamental part of a tree that stores data.
• Edge: The connection between two nodes.
• Root: The topmost node in a tree. It is the only node that does not have a parent.
• Parent: A node that has an edge to a child node.
• Child: A node that has a parent node.
• Leaf: A node that does not have any children.
• Subtree: A tree consisting of a node and its descendants.
• Depth (of a node): The number of edges from the root to the node.
• Height (of a tree): The number of edges on the longest path from the root to a leaf.

!Tree Terminology Diagram

Properties of a Tree

• There is one and only one path between any two nodes in a tree.
• A tree with N nodes will always have N-1 edges.
• It is a recursive data structure. Every child of a node is itself the root of a subtree.

Implementing a Generic Tree in Python

A common way to implement a generic tree is to create a TreeNode class. Each node will contain its data and a list of its children.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None
    def add_child(self, child):
        child.parent = self
        self.children.append(child)

--- Usage ---
root = TreeNode("Electronics")
laptop = TreeNode("Laptop")
laptop.add_child(TreeNode("Macbook"))
laptop.add_child(TreeNode("Surface"))
cellphone = TreeNode("Cell Phone")
cellphone.add_child(TreeNode("iPhone"))
cellphone.add_child(TreeNode("Google Pixel"))
root.add_child(laptop)
root.add_child(cellphone)
print("The root node is:", root.data)
print("Its children are:", [child.data for child in root.children])
print("The parent of 'Macbook' is:", laptop.data)

Types of Trees

There are many types of trees, each with specific properties and use cases. In the upcoming chapters, we will focus on the most common and important type:

• Binary Tree: A tree where each node has at most two children.
• Binary Search Tree (BST): A special type of binary tree where the data is kept in a sorted order.
• AVL Tree: A self-balancing binary search tree.
• Heaps: A specialized tree-based data structure that satisfies the heap property.

Trees are fundamental in computer science, used in everything from file systems and databases to AI and graphics.