Binary Trees

Analogy categoryAnalogies

Introduction

A binary tree is a hierarchical, non-linear data structure in which every node has at most two children, commonly referred to as the left child and the right child. Unlike arrays or linked lists, binary trees model relationships that branch, making them ideal for representing hierarchies such as file systems, organization charts, and expression parsing. The topmost node is called the root, and nodes with no children are called leaves. Binary trees form the conceptual base for more specialized structures like binary search trees, heaps, and AVL trees.

🏏

Cricket analogy: Think of a T20 tournament bracket where each match branches into at most two outcomes feeding the next round; the champion sits at the root and the first-round losers are leaves, unlike a batting lineup which is purely linear.

Structure/Syntax

python

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


# Manually building a small binary tree
#        1
#       / \
#      2   3
#     /
#    4
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

Explanation

Each TreeNode stores a value plus references to its left and right children, either of which may be None if that child does not exist. A node with no children is a leaf; a node's height is the number of edges on the longest path down to a leaf, and the tree's depth for a given node is the number of edges from the root to that node. Binary trees come in several important shapes: a full binary tree has every node with 0 or 2 children, a complete binary tree fills every level except possibly the last (left to right), and a perfect binary tree has all leaves at the same depth. These shape properties directly affect performance guarantees in structures built on top of binary trees.

🏏

Cricket analogy: A scorecard node for each over stores runs plus links to the next legal ball and the next dismissal event, either of which may be empty; a maiden over with no wickets is like a leaf with no children.

Example

python

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)


def height(node):
    if node is None:
        return -1  # empty tree has height -1
    return 1 + max(height(node.left), height(node.right))


print(count_nodes(root))  # total number of nodes
print(height(root))       # height of the tree

Complexity

Both count_nodes and height visit every node exactly once, giving O(n) time complexity where n is the number of nodes. Space complexity is O(h) due to the recursion call stack, where h is the height of the tree; in the worst case (a completely skewed tree that behaves like a linked list) h can be O(n), while in a balanced tree h is O(log n). Understanding this distinction between skewed and balanced trees is essential because it explains why balancing strategies (as in AVL trees) matter so much for performance.

🏏

Cricket analogy: Reviewing every ball of an innings takes time proportional to total balls bowled (O(n)), but the mental "stack" of overs you must hold in memory depends on how the innings unfolded — a lopsided one-sided partnership is like a skewed tree needing more memory than a balanced order.

Key Takeaways

A binary tree node has at most two children: left and right.
Full, complete, and perfect binary trees describe different shape guarantees.
Tree height ranges from O(log n) when balanced to O(n) when skewed.
Most tree algorithms are recursive and run in O(n) time, O(h) space.

Practice what you learned

1. What is the maximum number of children a node can have in a binary tree?

2. What is the height of an empty binary tree using the convention where a single-node tree has height 0?

3. Which type of binary tree has every level fully filled except possibly the last, which is filled left to right?

4. In the worst case, what is the height of a binary tree with n nodes?

Was this page helpful?

Binary Search Trees

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#BinaryTrees#Binary#Trees#Structure#Syntax#StudyNotes#SkillVeris