Tree

Definition

Consists of a collection of nodes (usually storing a value/element) connected by edges to form a hierarchical structure where nodes can have zero or more child nodes, except for a root node with no parent

Important caveats

• The edges in a tree are typically represented as pointers or references from parent nodes to child nodes
• The parent/child constraint means there are no cycles (loops)

Main operations

• add and remove

• search

• traverse (access/modify)

• height, depth

  • Usually implemented via DFS,BFS, recursive operations

• checkIfExists

• Optional: set operations, e.g.: union, intersection, difference

Implementation

Python tree with traversal code

class TreeNode:
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent
        self.children = []
 
    def add_child(self, child_node):
        child_node.parent = self
        self.children.append(child_node)
 
class Tree:
    def __init__(self, root):
        self.root = TreeNode(root)
 
    def print_tree(self, traversal_type):
        if traversal_type == "preorder":
            return self.preorder_traversal(self.root)
        elif traversal_type == "postorder":
            return self.postorder_traversal(self.root)
        elif traversal_type == "levelorder":
            return self.levelorder_traversal(self.root)
        else:
            print("Traversal type not supported.")
 
    def preorder_traversal(self, start):
        if start is None:
            return ""
 
        result = str(start.data) + " "
 
        for child in start.children:
            result += self.preorder_traversal(child)
 
        return result
 
    def postorder_traversal(self, start):
        if start is None:
            return ""
 
        result = ""
 
        for child in start.children:
            result += self.postorder_traversal(child)
 
        result += str(start.data) + " "
 
        return result
 
    def levelorder_traversal(self, start):
        if start is None:
            return ""
 
        queue = [start]
        result = ""
 
        while queue:
            node = queue.pop(0)
            result += str(node.data) + " "
 
            for child in node.children:
                queue.append(child)
 
        return result
 

• task Include operation details
• task Most of the page is incomplete