What is a Tree?

A Tree is a hierarchical data structure used to represent data.

A tree starts with a single node called the root and extends into several child nodes, each of which can have more child nodes.

Trees are used in various fields, such as file systems and search algorithms.

Basic Concepts and Key Terms of a Tree

Basic Concepts of a Tree

A tree consists of nodes and edges.

Nodes are units that store data, and edges represent the relationships between nodes.

The topmost node in a tree is called the root, and the tree expands from this root node into several child nodes.

Key Terms

• Root Node: The topmost node of the tree.

• Child Node: Nodes connected under the root node.

• Parent Node: Nodes that have child nodes.

• Leaf Node: Nodes without child nodes, located at the ends of the tree.

• Subtree: A part of the tree that starts with one node as its root.

• Depth: The length of the path from the root node to a specific node.

• Height: The length from the root node to the deepest leaf node.

Simple Tree Implementation in Python

There are various ways to implement trees, but for this lesson, we will introduce a simple structure called a binary tree.

A binary tree is a tree where each node can have a maximum of two child nodes.

The following binary tree has a root node 10, with a left child node 5, and a right child node 15.

Binary Tree Structure

       10
      /  \
     5    15

The following code implements a binary tree where data smaller than the root node is inserted into the left subtree, and equal to or larger data is inserted into the right subtree.

Simple Binary Tree Implementation Example

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_data):
        # Set the root node
        self.root = Node(root_data)

    def insert(self, current_node, data):
        # Insert data smaller than the root into the left subtree
        if data < current_node.data:
            if current_node.left is None:
                current_node.left = Node(data)
                print(f"{data} was added to the left of {current_node.data}.")
            else:
                self.insert(current_node.left, data)
        # Insert data equal to or larger than the root into the right subtree
        else:
            if current_node.right is None:
                current_node.right = Node(data)
                print(f"{data} was added to the right of {current_node.data}.")
            else:
                self.insert(current_node.right, data)

    def display(self, node, indent="", position="Root"):
        # Print current node
        if node is not None:
            print(indent + position + ": " + str(node.data))
            # Print left child node first (positioned below)
            self.display(node.left, indent + "   ", "L")
            # Print right child node (positioned below)
            self.display(node.right, indent + "   ", "R")

# Binary tree usage example
bt = BinaryTree(10)  # Set 10 as root node

bt.insert(bt.root, 5)  # Insert 5 to the left as it is smaller than 10

bt.insert(bt.root, 15)  # Insert 15 to the right as it is larger than 10

bt.insert(bt.root, 3)  # Insert 3 to the left of 5 as it is smaller

bt.insert(bt.root, 7)  # Insert 7 to the right of 5 as it is larger

bt.insert(bt.root, 13)  # Insert 13 to the left of 15 as it is smaller

bt.insert(bt.root, 17)  # Insert 17 to the right of 15 as it is larger

bt.display(bt.root)

Code Execution Result

Executing the code above generates the binary tree below, and each node's data is added to its position.

Output Result

Root: 10
   L: 5
      L: 3
      R: 7
   R: 15
      L: 13
      R: 17

In a binary tree, data is stored starting from the root node, branching into left and right subtrees.

Examples of Tree Structure Applications

Trees are used to solve various real-life problems.

• File Systems: The file structure in operating systems is represented by nodes as directories and files, with edges representing hierarchical relations.

• Search Algorithms: Using binary search trees can significantly improve data search speed.

• Document Structure: Document structures like HTML or XML are represented as trees, showing hierarchical relationships between elements.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.

Learn moreSign In