Binary tree

A binary tree has at most two children per node.

Binary tree

In a binary tree each node has at most two children: left and right. A complete binary tree has every level fully filled.

The node count count(node): 0 if None, else 1 + count(left) + count(right). This traverses the whole tree.

Inorder traversal: left → root → right. For a BST it gives increasing order.

Traversal types

There are three main traversal types: inorder (left-root-right), preorder (root-left-right), postorder (left-right-root). Each produces a different order.

Inorder gives sorted output on a BST. Preorder is used to copy a tree. Postorder processes children first and is ideal for deletion.

All run in O(n) and are written naturally with recursion; the code is short and readable.

Exercise Count nodes

Write count(node). 0 if None, else 1 + left + right. Print 3 with root = Node(1); root.left = Node(2); root.right = Node(3); print(count(root)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def count(node):
    # Count nodes
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(count(root))

Test yourself

Binary tree: match the terms

Binary tree

At most 2 children
Complete

Every level full
Inorder

Left-root-right
Count

1+left+right
What is the inorder traversal order?
- Root-left-right
- Right-root-left
- Left-right-root
- Left-root-right
Show answer

Left-root-right — Left-root-right

Node count

return 1 + count(node.left) + count(node.____)

Show answer

return 1 + count(node.left) + count(node.right)

Next lesson: Summary - Trees

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies