Binary tree
- Algorithms course
- Intermediate
- Lesson 27/80
- 4 min
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.
Practice 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)).
Starter code
def count(node):
# Count nodesSample 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))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Binary tree: match the terms
| Term | Meaning |
|---|---|
Binary tree |
At most 2 children |
Complete |
Every level full |
Inorder |
Left-root-right |
Count |
1+left+right |
2 What is the inorder traversal order?
- Root-left-right
- Right-root-left
- Left-right-root
- Left-root-right Correct answer
Explanation: Left-root-right
3 Node count
return 1 + count(node.left) + count(node.____)return 1 + count(node.left) + count(node.right)Explanation: right is right.