Binary Trees: Node Class Representation in Python

1. What is a Binary Tree?

Unlike linear data structures like arrays or linked lists which have a clear start and end, trees are hierarchical. Think of a family tree or an organizational chart.

A tree is a collection of entities called nodes, linked together by edges.

In this course, we will focus on a very common type of tree: the Binary Tree. The defining rule of a binary tree is simple: each node can have at most two children. These are referred to as the left child and the right child.

2. The Structure of a Node

To build a tree, we first need to define its fundamental building block: a single node. A node in a binary tree must hold three pieces of information:

1. The data it stores (e.g., a number, a string).
2. A reference (or "pointer") to its left child.
3. A reference (or "pointer") to its right child.

If a node does not have a left or right child, its corresponding reference will point to None.

This recursive definition—where a tree is made of nodes, and each node's pointers can point to other nodes that are themselves roots of smaller subtrees—is a core concept.

3. Creating a Node Class in Python

In Python, the most natural way to represent a custom object like a node is by using a class. We can create a Node class that encapsulates the three properties we just discussed.

The following video provides a concise explanation of what a binary tree is and how to define the Node class that forms its foundation.

As the video demonstrates, the implementation is straightforward. We define a class, often named Node or TreeNode, with a constructor (__init__) that sets up its attributes.

Here is the code for a basic Node class:

class Node:
    """
    A class to represent a single node in a binary tree.
    """
    def __init__(self, data):
        self.data = data   # The value stored in the node
        self.left = None   # A reference to the left child node
        self.right = None  # A reference to the right child node

When we create a new Node object, we must provide its data. The left and right children are initialized to None by default, signifying that the new node is initially a leaf node.

4. Building a Tree from Nodes

Now that we have our Node blueprint, we can create instances of it and link them together to form a tree. The entire tree structure can be accessed through a single variable that holds a reference to the root node.

Let's see how this is done in practice. The following resource provides a simple, concrete example.

Let's walk through building a simple tree ourselves. Suppose we want to create this tree:

    1
   / \
  2   3

Here's the Python code to do it:

# First, create the individual nodes
root = Node(1)
node2 = Node(2)
node3 = Node(3)

# Now, link them together
root.left = node2
root.right = node3

That's it! The variable root now holds a reference to the Node object with data 1. Through this root object, we can access the entire tree:

• root.data is 1.
• root.left points to the Node object with data 2.
• root.right points to the Node object with data 3.
• root.left.data is 2.
• root.left.left is None.

      50
     /  \
    25   75
   /
  10

# Define the Node class first
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Create the individual nodes
my_tree_root = Node(50)
node25 = Node(25)
node75 = Node(75)
node10 = Node(10)

# Link the nodes to form the tree
my_tree_root.left = node25
my_tree_root.right = node75
node25.left = node10

Conclusion

In this lesson, you've taken the first and most crucial step in working with trees: understanding how to represent them in code. This is the foundation upon which all other tree algorithms are built.

Key Takeaways:

• A binary tree is a hierarchical data structure where each node has at most two children (left and right).
• The fundamental unit of a tree is the node. We represent it in Python using a class.
• A Node class typically contains three attributes: data, left (a reference to the left child), and right (a reference to the right child). left and right are None if a child does not exist.
• We build a tree by creating instances of the Node class and linking them via their left and right attributes. The entire tree is accessed through a reference to the root node.

Up Next:
Now that we know how to build a tree, how do we visit every node within it? This process is known as tree traversal. In our next lesson, we will implement the three fundamental recursive traversal algorithms: preorder, inorder, and postorder. These are essential for solving a vast range of tree-based problems.