Trees and Binary Trees

This lesson covers trees and binary trees — hierarchical data structures that organise data in a parent-child relationship. Trees are used in file systems, databases, decision-making, and expression parsing.

---

What is a Tree?

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It has the following properties:

• There is exactly one root node (the top node with no parent).
• Every other node has exactly one parent.
• Nodes can have zero or more children.
• A node with no children is called a leaf (or terminal node).

Key Terminology

Term	Definition
Root	The topmost node in the tree (no parent).
Parent	A node that has one or more children.
Child	A node connected below a parent.
Leaf	A node with no children (also called a terminal node).
Edge	A connection between a parent and child node.
Subtree	A tree formed by a node and all its descendants.
Depth / Level	The number of edges from the root to a node. The root is at depth 0.
Height	The number of edges on the longest path from the root to a leaf.
Degree	The number of children a node has.

Example Tree

          A          ← Root (depth 0)
        / | \
       B  C  D       ← Depth 1
      / \    |
     E   F   G       ← Depth 2 (E, F, G are leaves)

• Root: A
• Leaves: E, F, C, G
• Height: 2
• Node B has degree 2 (children E and F)

---

Binary Trees

A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child.

        10
       /  \
      5    15
     / \     \
    3   7    20

Properties of Binary Trees

Property	Description
Maximum nodes at depth d	2^d
Maximum total nodes (height h)	2^(h+1) - 1
Minimum height for n nodes	floor(log2(n))

Types of Binary Trees

Type	Description
Full binary tree	Every node has either 0 or 2 children (no node has exactly 1 child).
Complete binary tree	All levels are fully filled except possibly the last, which is filled from left to right.
Balanced binary tree	The height of the left and right subtrees of every node differs by at most 1.
Degenerate (skewed) tree	Every node has only one child, essentially forming a linked list.

---

Binary Tree Node Implementation

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

Building a Simple Tree

# Create nodes
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(20)

#         10
#        /  \
#       5    15
#      / \     \
#     3   7    20

---

Tree Traversals