Skip to content
Laviyx Learn

Try

DSA course menu

Trees and Binary Trees: Terminology and Python Implementation

Learn the tree data structure: root, parent, child, leaf, depth and height, binary trees and their types, building a binary tree in Python, and computing size, height and leaf count recursively.

Intermediate9 min readUpdated
On this page

A tree stores data in a hierarchy: one item at the top branches into children, which branch into their own children, and so on. File systems, HTML pages, company org charts and the moves in a game are all trees.

Text
            CEO                 ← root
          /     \
       CTO       CFO
      /   \         \
   Dev1   Dev2     Accountant   ← leaves

Vocabulary#

TermMeaning
nodeone item in the tree
rootthe top node; it has no parent
parent / childa node directly above / below another
leafa node with no children
edgethe link between a parent and a child
depth of a nodenumber of edges from the root down to it (root has depth 0)
height of a treenumber of edges on the longest path from the root to a leaf
subtreea node together with everything below it

A tree with n nodes always has exactly n − 1 edges, and there is exactly one path between any two nodes.

Binary trees#

In a binary tree, every node has at most two children, called left and right. It is the most important kind of tree in DSA.

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

#        1
#       / \
#      2   3
#     / \    \
#    4   5    6
root = TreeNode(1,
                TreeNode(2, TreeNode(4), TreeNode(5)),
                TreeNode(3, None, TreeNode(6)))

print(root.value, root.left.value, root.right.right.value)
Output
1 2 6

Thinking recursively about trees#

Every subtree is itself a tree, so most tree functions follow one recipe: handle the empty tree, then combine the answers for the left and right subtrees.

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

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

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

def height(node):
    if node is None:
        return -1                 # so a single node has height 0
    return 1 + max(height(node.left), height(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)

def tree_sum(node):
    return 0 if node is None else node.value + tree_sum(node.left) + tree_sum(node.right)

print("size", size(root))
print("height", height(root))
print("leaves", count_leaves(root))
print("sum", tree_sum(root))
Output
size 6
height 2
leaves 3
sum 21

Each function visits every node once: O(n) time, and O(h) stack space for a tree of height h.

Types of binary trees#

  • Full: every node has 0 or 2 children.
  • Complete: every level is completely filled except possibly the last, which is filled from the left. Heaps are complete trees.
  • Perfect: all internal nodes have 2 children and all leaves are at the same depth. A perfect tree of height h has 2^(h+1) − 1 nodes.
  • Balanced: the heights of the left and right subtrees of every node differ by at most 1. Balanced trees have height O(log n).
  • Degenerate: every node has one child, so the tree is really a linked list with height n − 1.

The height matters because most tree operations cost O(h). With a million nodes, a balanced tree is about 20 levels deep; a degenerate one is a million.

Python
import math
for n in [7, 1_000, 1_000_000]:
    print(f"{n:>9} nodes: balanced height ~{math.floor(math.log2(n))}, degenerate height {n - 1}")
Output
        7 nodes: balanced height ~2, degenerate height 6
     1000 nodes: balanced height ~9, degenerate height 999
  1000000 nodes: balanced height ~19, degenerate height 999999

Common mistakes#

Practice#

Practice exercise

Write max_value(node) that returns the largest value in a binary tree (or None for an empty tree), and mirror(node) that swaps the left and right children of every node in place.

Show hint

max_value: compare the node's value with the maximum of each non-empty subtree. mirror: swap node.left and node.right, then mirror both subtrees.

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

def max_value(node):
    if node is None:
        return None
    best = node.value
    for child in (node.left, node.right):
        m = max_value(child)
        if m is not None and m > best:
            best = m
    return best

def mirror(node):
    if node is not None:
        node.left, node.right = node.right, node.left
        mirror(node.left)
        mirror(node.right)

def show(node):
    if node is None:
        return "."
    return f"({show(node.left)} {node.value} {show(node.right)})"

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(9)), TreeNode(3))
print(max_value(root))
print(show(root))
mirror(root)
print(show(root))
Output
9
(((. 4 .) 2 (. 9 .)) 1 (. 3 .))
((. 3 .) 1 ((. 9 .) 2 (. 4 .)))

Key takeaway#

Next: the different orders for visiting nodes, Tree Traversals.

Finished this lesson?

Related lessons

DSATree Traversals: Preorder, Inorder, Postorder and Level OrderLearn binary tree traversals in Python: preorder, inorder and postorder (recursive and iterative with a stack), level-order traversal with a queue, and what each order is used for.Intermediate11 min readDSABinary Search Trees (BST) in Python: Insert, Search and DeleteLearn binary search trees: the BST property, searching and inserting in O(h), deleting nodes with zero, one or two children, validating a BST, and why unbalanced BSTs become slow.Intermediate15 min readDSARecursion for DSA: Base Cases, Call Stack and MemoizationUnderstand recursion for data structures and algorithms: base and recursive cases, how the call stack works, recursion trees, the cost of naive Fibonacci, and memoization with lru_cache.Beginner9 min readDSAHeaps and Priority Queues in Python (heapq Explained)Learn the heap data structure: min-heaps and max-heaps, storing a complete tree in an array, sift up and sift down, building a heap in O(n), Python's heapq module, heap sort and top-k problems.Intermediate10 min read