Lesson 8 · Non-linear structures

Binary Trees

A Binary Tree is a hierarchical structure where every node has at most two children, forming the basis for complex search and routing algorithms.

Hierarchical Memory

Unlike arrays and linked lists that store data in a linear sequence, trees represent data hierarchically. A Binary Tree restricts this hierarchy so that any given node points to no more than two subsequent nodes, commonly referred to as the 'left' and 'right' children.

Roots, Branches, and Leaves

The top node is the root, the origin of all paths. Nodes with no children are called leaves. The depth of a node is the number of edges from the root to it, and the height of the tree is the maximum depth across all leaves. Understanding these properties is crucial for bounding traversal algorithms.

Key reference

Terms, operations, and practical uses

Tree Properties

Root NodeThe singular topmost node of a tree, which has no parent.
Leaf NodeA node located at the bottom of the tree, characterized by having exactly zero children.
Internal NodeAny node that is not a leaf; it has at least one child.

Metrics

Node DepthThe number of edges on the path from the root node to a specific node.
Tree HeightThe maximum depth across all nodes in the tree. An empty tree has height -1, and a single node has height 0.
SubtreeA node and all of its descendants, which independently forms a valid tree structure.

Structural Types

Full Binary TreeA binary tree in which every node has either zero or exactly two children.
Complete Binary TreeA binary tree where every level is fully filled, except possibly the last, which is filled left-to-right.
Perfect Binary TreeA binary tree where all internal nodes have two children and all leaves are at the exact same depth.

Code example

Build a three-node binary tree

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

root = TreeNode(1, TreeNode(2), TreeNode(3))
print('Root:', root.val)

struct BinaryTreeNode {
    int val;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    BinaryTreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

BinaryTreeNode* buildExampleTree() {
    BinaryTreeNode* root = new BinaryTreeNode(1);
    root->left = new BinaryTreeNode(2);
    root->right = new BinaryTreeNode(3);
    return root;
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

Inputroot = 1, left = 2, right = 3

OutputRoot: 1

Example

Run the example step by step

Output

Recursion in Trees

Trees are inherently recursive. Every child of a node is the root of its own smaller subtree. This property makes recursive functions the most natural way to traverse, count, or modify the tree, as the same operation applied to the root can be applied identically to the left and right children.

Types of Binary Trees

A binary tree can be 'full' (every node has 0 or 2 children), 'complete' (every level is completely filled except possibly the last, which is filled left-to-right), or 'perfect' (all interior nodes have 2 children and leaves are at the same depth). Complete trees are particularly useful for array-based heaps.