Binary Trees
Trees & BST: lesson 2 of 8
At most two children: one left, one right, never swapped.
Lesson 2 of 8 · 4 min
Binary Trees
Step 1 of 11
A binary node has exactly two child slots: left and right. Never three.
The Idea
A binary tree gives every node exactly two child slots: left and right. Either slot may sit empty, and the two are not interchangeable, so swapping them produces a different tree. That fixed shape is what lets an algorithm say "go left" and mean something precise.
Real-World Example
A TV aerial splitter. One cable feeds in and two run out, and each output can feed another splitter or go straight to a set. Nothing ever merges back together, and the two sockets are physically distinct, not a pair you can swap.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
# every node has at most two children: left and right
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
def count(n):
if n is None: return 0 # an empty slot contributes nothing
return 1 + count(n.left) + count(n.right)
print(root.left.val, root.right.val) # 2 3
print(root.left.left.val) # 4
print(root.right.left) # None -> that slot is empty
print(count(root)) # 5 nodes in totalYour turn
Put the steps in the right order.
- Recursively count the left subtree
- Return 0 when the node is empty
- Add one for this node and return the total
- Recursively count the right subtree
Mini quiz
1 / 3