Binary Trees in DSA: Introduction

Beginner 11 min read

What you'll learn

✓What a binary tree is and how to model one in Python
✓The vocabulary — root, leaf, parent, child, subtree
✓Full, complete, perfect, and balanced trees — the differences
✓Height vs depth, and how to calculate both
✓How a Binary Search Tree differs from a general binary tree
✓The shape calculations you keep needing in interviews

Prerequisites

•Comfortable with Classes and Objects and basic recursion

A binary tree is a recursive data structure where each node holds a value and points to at most two children. They show up everywhere — file systems, expression parsers, decision trees, database indexes, and a large chunk of interview questions. This post sets up the vocabulary, the Python representation, and the small calculations you’ll be asked about over and over.

What is a binary tree?

A binary tree is a collection of nodes where each node has:

A value
A reference to a left child (or None)
A reference to a right child (or None)

There is one special node — the root — that no other node points to. From the root, the tree branches outward.

        1            <- root
       / \
      2   3
     / \   \
    4   5   6        <- leaves: 4, 5, 6

A node with no children is a leaf. A node directly above another is its parent; the node below is its child. Any node together with everything reachable below it is called a subtree.

The TreeNode class

The standard Python representation is a small class:

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

    def __repr__(self):
        return f"TreeNode({self.value})"

Building the tree above looks like this:

root = TreeNode(1,
    left=TreeNode(2, TreeNode(4), TreeNode(5)),
    right=TreeNode(3, None, TreeNode(6)),
)

That’s it — the entire shape of a tree is captured by where each node’s left and right point.

Vocabulary

A handful of terms you’ll keep meeting:

Root — the topmost node; the one with no parent.
Leaf — a node with no children (both left and right are None).
Internal node — any non-leaf node.
Edge — the link between a parent and a child.
Path — a sequence of nodes connected by edges.
Depth of a node — the number of edges from the root to that node. The root has depth 0.
Height of a node — the number of edges on the longest path from that node down to a leaf. A leaf has height 0.
Height of the tree — the height of the root.
Level — all nodes at the same depth form a level. Level 0 is just the root.

Depth grows downward; height grows upward. They meet at the leaves.

Special shapes

Not every binary tree is shaped the same, and a few shapes have names worth knowing.

Full binary tree

Every node has either 0 or 2 children. No node has exactly one child.

Complete binary tree

Every level is completely filled except possibly the last, and the last level is filled left to right.

Complete trees are the shape used by binary heaps — they pack neatly into arrays.

Perfect binary tree

All internal nodes have two children and all leaves are at the same depth.

A perfect tree of height h has exactly 2^(h+1) - 1 nodes.

Balanced binary tree

For every node, the heights of its left and right subtrees differ by at most 1. Balanced trees keep operations like search at O(log n) instead of degrading to O(n).

       1
      / \
     2   3
    /     \
   4       5     <- still balanced (heights differ by 1 at most)

A skewed tree — every node has only a left child, or only a right child — is the worst case. It is essentially a linked list.

Try it yourself. Build the four shapes above using the TreeNode class. Then write a one-line description of each: number of nodes, number of leaves, and height. This makes the definitions stick faster than re-reading them.

Height and depth — calculated

Both are computed recursively. Here is height of a tree (number of edges on the longest root-to-leaf path):

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

print(height(root))    # 2

If you prefer to count nodes on the path instead of edges (some textbooks do), use 0 for the base case and the answer becomes height + 1. Pick a convention and stick to it.

Depth of a target node is computed top-down — you pass the current depth as you descend:

def depth(node, target, current=0):
    if node is None:
        return -1
    if node is target:
        return current
    left = depth(node.left, target, current + 1)
    if left != -1:
        return left
    return depth(node.right, target, current + 1)

Counting nodes and leaves

Two of the most common warm-up problems:

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

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

print(count_nodes(root))     # 6
print(count_leaves(root))    # 3

Notice the pattern: a recursive tree function returns something for None, returns something for a leaf, and otherwise combines the results from the left and right subtrees. Almost every tree question fits this mould.

Binary Search Trees

A Binary Search Tree (BST) is a binary tree with an extra rule: for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater.

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

This ordering means you can search a BST by walking down from the root, going left when your target is smaller and right when it’s larger:

def bst_search(node, target):
    if node is None:
        return False
    if target == node.value:
        return True
    if target < node.value:
        return bst_search(node.left, target)
    return bst_search(node.right, target)

On a balanced BST this runs in O(log n). On a skewed BST it degrades to O(n) — which is why self-balancing variants like AVL and Red-Black trees exist.

A general binary tree has no ordering rule. Any value can sit anywhere. The BST rule is what unlocks fast lookups.

Shape calculations you’ll be asked

A few formulas that come up in interviews:

A perfect binary tree of height h has 2^(h+1) - 1 nodes and 2^h leaves.
A binary tree with n nodes has height at least floor(log2(n)) and at most n - 1.
A binary tree with n nodes has n - 1 edges (every node except the root has exactly one parent edge).
In a full binary tree, the number of leaves equals (internal nodes) + 1.

You don’t have to memorize these — derive them once each and they stick.

Try it yourself. Write a function is_balanced(node) that returns True if a tree is height-balanced. Hint: do it in O(n) by returning the height up the recursion and using -1 as a sentinel for “unbalanced subtree found below.”

A worked example

Build a small tree and answer the standard questions about it:

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

#         10
#        /  \
#       5    15
#      / \     \
#     3   7    20
root = TreeNode(10,
    TreeNode(5, TreeNode(3), TreeNode(7)),
    TreeNode(15, None, TreeNode(20)),
)

def height(n):
    if n is None: return -1
    return 1 + max(height(n.left), height(n.right))

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

def count_leaves(n):
    if n is None: return 0
    if n.left is None and n.right is None: return 1
    return count_leaves(n.left) + count_leaves(n.right)

print(height(root))         # 2
print(count_nodes(root))    # 6
print(count_leaves(root))   # 3

This is the shape of nearly every tree-warming question. Once you can write these in your sleep, you’re ready for traversals.

When to use a binary tree

Reach for a binary tree when:

The data is naturally hierarchical (file systems, organisation charts, comment threads).
You need ordered lookups and a balanced BST fits — though in Python, dict and sorted containers usually beat hand-rolled BSTs in practice.
You’re modelling a decision process or an expression with two operands per operator.
You’re implementing a heap, a segment tree, or another array-backed tree structure.

For most everyday Python work, the built-in containers do the job. Trees come into their own in systems programming, databases, and when the problem itself is a tree.

Recap

You now know:

A binary tree is nodes with up to two children, modelled by a small TreeNode class
Vocabulary: root, leaf, internal node, edge, path, depth, height, level
Full, complete, perfect, and balanced are four named shapes with distinct meanings
Height counts edges upward; depth counts edges from the root downward
A BST adds the rule “left < node < right” to enable O(log n) search on balanced trees
The recursive shape of tree functions: base for None, base for leaf, combine subtrees

Next steps

The next post covers the four canonical ways to walk a binary tree — inorder, preorder, postorder, and level-order. Traversals are the foundation for almost every tree algorithm, and getting fluent with them pays off for the rest of the series.

→ Next: Binary Tree Traversals

Questions or feedback? Email codeloomdevv@gmail.com.