DSA Tree Vocabulary

A binary tree is a structure where each node holds one value and has at most two children. The names for its parts and measures are the vocabulary that every tree lesson uses.

One node on its own

A node is one holder in the tree. It stores a value and two child slots, and None marks an empty slot.

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


node = TreeNode(5)
print("Value:", node.value)
print("Left child:", node.left)
print("Right child:", node.right)

A root with two children

The root is the top node of the tree. The links joining a parent to a child are edges.

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


root = TreeNode(8, TreeNode(3), TreeNode(10))
print("Root:", root.value)
print("Left child:", root.left.value)
print("Right child:", root.right.value)

Finding the leaves

A leaf is a node with no children. This walk collects the leaves of a small tree from left to right.

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


def collect_leaves(node, found):
    if node is None:
        return
    if node.left is None and node.right is None:
        found.append(node.value)
    collect_leaves(node.left, found)
    collect_leaves(node.right, found)


tree = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10))
found = []
collect_leaves(tree, found)
print("Leaves:", found)

Example

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


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


def collect_leaves(node, found):
    if node is None:
        return
    if node.left is None and node.right is None:
        found.append(node.value)
    collect_leaves(node.left, found)
    collect_leaves(node.right, found)


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


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


tree = TreeNode(8,
                TreeNode(3, TreeNode(1), TreeNode(6)),
                TreeNode(10, None, TreeNode(14)))

leaves = []
collect_leaves(tree, leaves)
nodes = count_nodes(tree)

print("Root:", tree.value)
print("Nodes:", nodes)
print("Edges:", nodes - 1)
print("Leaves:", leaves)
print("Height:", height(tree))
print("Depth of node 6:", depth_of(tree, 6))

Key points

Binary tree: each node has at most two children, named the left child and the right child
Root: the single node at the top of the tree, with no parent
Leaf: a node with no children
Subtree: a node together with everything below it, read as a smaller tree
Depth: how many edges separate a node from the root
Height: the depth of the deepest leaf in the tree
Ancestor: any node on the path from the root down to a node's parent
A tree with n nodes always has n - 1 edges

In this example, the tree has root 8, with 3 and 10 below it and 14 hanging under 10. The count walks every node once and finds six nodes. Six nodes give five edges, one link per node except the root. The leaf walk collects 1, 6 and 14, the three nodes with no children. The height comes out as 2, matching the depth of node 6, which sits two edges below the root.

Note

Python has no built-in tree type, so this series builds every tree from the TreeNode class shown here

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

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


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


def collect_leaves(node, found):
    if node is None:
        return
    if node.left is None and node.right is None:
        found.append(node.value)
    collect_leaves(node.left, found)
    collect_leaves(node.right, found)


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


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


tree = TreeNode(8,
                TreeNode(3, TreeNode(1), TreeNode(6)),
                TreeNode(10, None, TreeNode(14)))

leaves = []
collect_leaves(tree, leaves)
nodes = count_nodes(tree)

print("Root:", tree.value)
print("Nodes:", nodes)
print("Edges:", nodes - 1)
print("Leaves:", leaves)
print("Height:", height(tree))
print("Depth of node 6:", depth_of(tree, 6))

Exercise

In the closing example's tree, which of these values sits on a leaf?

3 8 10 14