beginnerintermediateadvanced

Data Structures & Algorithms · Section 14

Trees

Level: beginner
Read: 90 min
Concepts: 12

Tree terminology and the binary tree shape, the BST ordering invariant and why it must hold against every ancestor, why balance decides whether operations are O(log n) or O(n), BST insert/search/delete, validating a BST correctly, finding a lowest common ancestor, computing height and depth, a tree's diameter, checking balance, serializing a tree conceptually, and n-ary trees as the generalization beyond two children.

What is true here

A binary tree is a chain of nodes that branches — each node has up to two children, left and right.
A BST adds one global rule: left subtree entirely smaller, right subtree entirely larger, against every ancestor, not just the immediate parent.
Balance determines whether BST operations cost O(log n) or degrade to O(n) — a plain BST offers no guarantee either way.
Almost every tree algorithm shares the same recursive skeleton: a None base case, then combine what the left and right subtrees report.

What you will be able to do

Build a binary tree and a BST, and explain the extra invariant that separates them
Insert, search, and delete from a BST, including the two-children deletion case
Validate a BST correctly using an inherited range, and explain why checking only the immediate parent is not enough
Compute height, depth, diameter, and balance in a single bottom-up pass each

Concepts

From tree terminology and the binary-tree shape, through the BST invariant and its three core operations, to lowest common ancestor, height/depth/diameter/balance, serialization, and the n-ary generalization.

Tree terminology: root, leaf, height, depth, subtree

referencebeginner

A tree is nodes connected by edges with no cycles — one root, and every other node reachable from it by exactly one path. A leaf has no children; height is measured down to the farthest leaf; depth is measured up to the root; a subtree is any node treated as the root of its own smaller tree.

tree_terms.pypython

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


#         1              <- root (depth 0)
#        / \
#       2   3            <- 2 and 3 have depth 1
#      /
#     4                  <- leaf, depth 2; the tree's height is 2
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))

Remember: height looks down to the farthest leaf, depth looks up to the root — a leaf always has height 0, and the root always has depth 0.

Was this helpful?

Binary tree

corebeginner

A binary tree is a tree where every node has AT MOST two children, conventionally called left and right — there is no ordering rule between them, unlike a binary search tree.

Think of it as

Think of it as a linked list where each node has two next pointers instead of one. There is no rule about which values go left vs right — that extra constraint is what turns a plain binary tree into a binary SEARCH tree. Recursion is the natural fit for almost every binary-tree operation, because a tree is, by definition, built from two smaller trees — its own left and right subtrees.

What we're doing: Build a small binary tree and count its nodes recursively.

binary_tree.pypython

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)


root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(count_nodes(root))
print(count_nodes(root.left))

8: The base case: an empty subtree contributes 0 nodes — this is what stops the recursion.
9: A node counts itself, plus whatever its left and right subtrees report — the same shape as almost every tree function.

Output

4
2

Why this works: The full tree has 4 nodes (1, 2, 3, 4). root.left is the 2-node subtree rooted at 2 (which has one child, 4) — count_nodes counts it as 2 nodes on its own, independent of the rest of the tree.

Recursing without a base case for None

Wrong

python

def count_nodes_wrong(node):
    return 1 + count_nodes_wrong(node.left) + count_nodes_wrong(node.right)


root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(count_nodes_wrong(root))

Better

python

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

What you see: count_nodes_wrong(root) raises AttributeError: 'NoneType' object has no attribute 'left' — it crashes instead of returning a count.

Why: Every real node eventually has at least one None child (a leaf's left and right are both None). Without a base case that returns immediately on None, the recursion tries to read .left and .right off None itself, the moment it reaches a leaf's missing child.

Remember: Every binary-tree function needs a None base case first — a real node always bottoms out at a missing child, and that is exactly where the recursion has to stop instead of dereferencing it.

Was this helpful?

Binary search tree (BST) and its ordering invariant

corebeginner

A BST is a binary tree with one extra rule: for every node, everything in its LEFT subtree is smaller, and everything in its RIGHT subtree is larger — not just its immediate children, the ENTIRE subtree.

Think of it as

The invariant is GLOBAL, not local — a node two levels down still has to respect the ordering relative to every ancestor above it, not just its immediate parent. This is exactly the subtlety that makes validating a BST harder than it first looks: a node can look fine next to its own parent while still breaking the rule against a grandparent or the root.

What we're doing: Confirm the ordering invariant holds by checking that an inorder traversal of a real BST comes out sorted.

bst_invariant.pypython

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


def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)


#        5
#       / \
#      3   8
#     / \
#    1   4
root = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))

values = []
inorder(root, values)
print(values)

17: 3 is less than 5, and both 1 and 4 (its entire subtree) are less than 5 too — not just less than 3, their immediate parent.

Output

[1, 3, 4, 5, 8]

Why this works: Visiting left-subtree, then the node itself, then right-subtree, at every level, means every value that is smaller than the root is visited before it, and every larger value after — the invariant is exactly what guarantees the result comes out sorted.

Building a tree that is only LOCALLY correct, not globally

Wrong

python

# Looks locally fine at every node — 1 < 3, 6 > 3, 8 > 5 — but 6
# sits in 5's LEFT subtree while being greater than 5, violating
# the GLOBAL invariant.
broken = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(8))

values = []
inorder(broken, values)
print(values)

Better

python

root = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))

What you see: inorder(broken, values) returns [1, 3, 6, 5, 8] — not sorted, even though every node's immediate left/right child looks locally fine.

Why: 6 sits in 5's LEFT subtree, so the invariant requires 6 < 5 — but 6 > 5. Checking only whether a node beats its immediate parent misses violations buried deeper in the subtree. The invariant must hold against every ancestor, not just the one directly above — exactly the trap that validating a BST is built to catch.

Remember: Left subtree entirely smaller, right subtree entirely larger — against every ancestor, not just the immediate parent. Inorder traversal is the invariant made visible: it always comes out sorted.

Balanced vs unbalanced trees (why balance matters for complexity)

standardintermediate

A balanced tree keeps its height close to log2(n) for n nodes, so search/insert/delete stay O(log n). An unbalanced tree can degrade toward a straight line — height n — making the same operations O(n), no better than a linked list.

Think of it as

Balance is about the SHAPE of the tree, not its values. Inserting sorted data (1, 2, 3, 4, 5...) one at a time into a plain BST with no rebalancing produces a tree that is really a linked list wearing a tree's clothes — every node ends up with only a right child.

What we're doing: Compare the height of a balanced tree against a degenerate one built from the same 5 values, inserted in sorted order.

balance_comparison.pypython

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


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


balanced = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4, None, TreeNode(5)))
degenerate = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))))

print(height(balanced))
print(height(degenerate))

16: Both trees hold the same 5 values (1 through 5) — only the SHAPE differs.
17: degenerate chains every node to the right, exactly as sorted-order insertion into a plain BST would produce.

Output

2
4

Why this works: balanced spreads 5 nodes across a height of 2, close to the log2(5) ≈ 2.3 a balanced shape targets. degenerate is a straight chain — height 4, which is n - 1 for 5 nodes — the exact worst case a plain BST offers no protection against.

Remember: Balance is about shape, not values — the same values inserted in a different order can turn an O(log n) tree into an O(n) chain, and a plain BST does nothing to stop it.

Was this helpful?

BST insert, search, delete

coreintermediate

Insert and search both use the ordering invariant to pick a direction at every node — smaller goes left, larger goes right — until they hit the target or an empty spot. Delete is the same idea, plus three cases for what to do once the node to remove is actually found.

Think of it as

Insert and search are nearly identical: at each node, compare the target to node.value and recurse left or right, stopping at None (insert: attach a new node there; search: report not found). Delete has to handle what is LEFT BEHIND once a node is removed — a leaf just vanishes, a node with one child is replaced by that child, and a node with two children is replaced by its INORDER SUCCESSOR (the smallest value in its right subtree), which is then removed from where it used to be.

What we're doing: Build a small BST by inserting values one at a time, search it, then delete a node that has two children.

bst_operations.pypython

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


def insert(node, value):
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def search(node, value):
    if node is None:
        return False
    if value == node.value:
        return True
    if value < node.value:
        return search(node.left, value)
    return search(node.right, value)


def delete(node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = node.right
        while successor.left:
            successor = successor.left
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node


def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)


root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)

print(search(root, 4))
print(search(root, 7))

root = delete(root, 3)
values = []
inorder(root, values)
print(values)

8: insert returns a node every time — the caller reassigns node.left/node.right to whatever comes back, which is how a brand-new node actually gets attached.
30: The two-children case: successor walks as far left as possible in the right subtree, finding the smallest value greater than node.value.

Output

True
False
[1, 4, 5, 8]

Why this works: Inserting 5, 3, 8, 1, 4 builds 5 with left subtree 3 (children 1, 4) and right child 8. search finds 4 (present) and correctly reports 7 as absent. Deleting 3 — a two-children node — replaces its value with its successor, 4, then removes the original 4 from the right side of that subtree, leaving [1, 4, 5, 8] in sorted order.

Discarding insert's return value instead of reassigning it

Wrong

python

def insert_wrong(node, value):
    if node is None:
        node = TreeNode(value)   # only rebinds the LOCAL variable `node`
    elif value < node.value:
        insert_wrong(node.left, value)   # return value discarded
    elif value > node.value:
        insert_wrong(node.right, value)  # return value discarded


root = None
insert_wrong(root, 5)
print(root)

root = TreeNode(5)
insert_wrong(root, 3)
print(root.left)

Better

python

def insert(node, value):
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

What you see: Both root (after "inserting" into an empty tree) and root.left (after "inserting" a smaller value) print None — neither insertion actually took effect, and no error is raised.

Why: Python passes object references by value — reassigning the parameter node inside the function only rebinds that function's own local variable, never what the CALLER's variable points at. The working insert() only succeeds because every call site captures the return value (node.left = insert(node.left, value)) — the caller does the rebinding explicitly, the callee cannot do it for them.

Search in a Binary Search TreeeasyLeetCode
Exactly the search function above — follow the ordering invariant down to a match or None.
Delete Node in a BSTmediumLeetCode
Exactly the delete function above — the three cases (leaf, one child, two children) handle every shape the node to remove can take.

Remember: Insert and search both follow the ordering invariant down to a None or a match; delete additionally has to relink around whatever it removes — always reassign a recursive call's return value, never call it and discard it.

Was this helpful?

Validating a BST

coreintermediate

The naive instinct — compare each node only to its immediate children — misses violations buried deeper in the tree. The correct approach carries a valid (low, high) range down through the recursion, so every node is checked against ALL of its ancestors, not just its direct parent.

Think of it as

Each recursive call is handed the range its node is allowed to fall in, inherited from every decision made above it. Going left tightens the upper bound to the current node's value; going right tightens the lower bound. A node fails the moment its own value falls outside the range it inherited — however locally reasonable it looks next to its immediate parent.

What we're doing: Validate a genuinely correct BST and a broken one, using an inherited (low, high) range.

is_valid_bst.pypython

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


def is_valid_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.value < high):
        return False
    return is_valid_bst(node.left, low, node.value) and is_valid_bst(node.right, node.value, high)


valid = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))
invalid = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(8))

print(is_valid_bst(valid))
print(is_valid_bst(invalid))

8: The default range is unbounded — only the root call relies on these defaults.
9: not (low < node.value < high) fails the instant a node falls outside the range it inherited, from ANY ancestor, not just its parent.
10: Going left tightens high to the current value; going right tightens low — the range narrows on every step down.

Output

True
False

Why this works: invalid puts 6 in 5's left subtree. By the time the recursion reaches 6, its inherited range is (3, 5) — narrowed by both its parent (3) and the root (5) — and 6 fails that range immediately, even though 6 is perfectly fine relative to its own immediate parent.

Checking only the immediate parent/children, not the inherited range

Wrong

python

def is_valid_bst_wrong(node):
    if node is None:
        return True
    if node.left and node.left.value >= node.value:
        return False
    if node.right and node.right.value <= node.value:
        return False
    return is_valid_bst_wrong(node.left) and is_valid_bst_wrong(node.right)


invalid = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(8))
print(is_valid_bst_wrong(invalid))

Better

python

def is_valid_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.value < high):
        return False
    return is_valid_bst(node.left, low, node.value) and is_valid_bst(node.right, node.value, high)

What you see: is_valid_bst_wrong(invalid) returns True — for the exact same tree the range-based version correctly rejects.

Why: 6's immediate parent is 3, and 6 > 3, so the local check node.right.value <= node.value passes without complaint. The function never checks 6 against 5, its grandparent — which is where the actual violation lives. Local correctness at every node does not add up to global correctness.

Validate Binary Search TreemediumLeetCode
Exactly the example above — the inherited (low, high) range, tightened on every step down.
Minimum Absolute Difference in BSTeasyLeetCode
Uses the same underlying fact this concept relies on: an inorder traversal of a valid BST is sorted, so the minimum difference is always between two INORDER-adjacent values.

Remember: Carry a (low, high) range down through the recursion, tightened by every ancestor along the way — checking only the immediate parent is the single most common way to ship a broken BST validator.

Was this helpful?

Lowest common ancestor (BST and general binary tree versions)

standardintermediate

The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them somewhere in its subtree — possibly being one of the two targets itself.

Think of it as

On a general binary tree, recursion finds it naturally: search both subtrees for the two targets. If a node's LEFT search and RIGHT search each find one target, that node is the split point — the LCA. If only one side finds anything, the LCA must be further down that side.

What we're doing: Find the lowest common ancestor of two nodes in a general binary tree.

lca.pypython

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


def lowest_common_ancestor(node, p, q):
    if node is None or node.value == p or node.value == q:
        return node
    left = lowest_common_ancestor(node.left, p, q)
    right = lowest_common_ancestor(node.right, p, q)
    if left and right:
        return node
    return left if left else right


root = TreeNode(3, TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4))), TreeNode(1, TreeNode(0), TreeNode(8)))

print(lowest_common_ancestor(root, 5, 1).value)
print(lowest_common_ancestor(root, 6, 4).value)

9: Hitting either target, or running off the tree entirely, both bubble straight back up — a match does not need to search any further down.
11: If BOTH sides report finding something, the targets are split across this node's two subtrees — this node is the LCA.

Output

3
5

Why this works: 5 and 1 sit in different subtrees of the root (3), so the root itself is their LCA. 6 and 4 are both underneath 5 — 6 directly, 4 through 5's right subtree — so 5, the deepest node covering both, is their LCA.

Remember: If a node's left search and right search each find one target, that node is the LCA. On a BST, skip the search entirely — the invariant tells you which direction to go at every step.

Was this helpful?

Computing height/depth

standardintermediate

height is measured DOWN from a node to its farthest leaf; depth is measured UP from a node to the root. A recursive height function is bottom-up — it needs both children's answers before it can compute its own. Finding a specific node's depth is top-down — a search from the root, counting steps as it descends.

Think of it as

height(node) recurses first, then combines: 1 + max(height(left), height(right)) cannot be computed until both recursive calls return. depth(node, target) is the opposite shape — it decides what to return as it goes, tracking a running level count down from the root, and stops the instant it finds the target.

What we're doing: Compute a node's height (looking down) and another node's depth (looking up from the root).

height_and_depth.pypython

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


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


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


root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))

print(height(root))
print(height(root.left))
print(depth(root, 4))

8: height bottoms out at -1 for an empty subtree — a leaf is then 1 + max(-1, -1) = 0.
15: depth counts UPWARD in spirit by counting DOWNWARD from the root — level starts at 0 and increases by 1 on every step deeper.

Output

2
1
2

Why this works: The full tree (1, with 2→4 on the left, 3 on the right) has height 2 — the path 1→2→4 is 2 edges long. root.left (the subtree rooted at 2) has height 1 on its own. Node 4 sits 2 levels below the root, so its depth is 2.

Remember: height looks down and combines both children's answers; depth looks up (implemented as a top-down search from the root) and stops the moment it finds the target.

Was this helpful?

Diameter of a binary tree

standardintermediate

The diameter is the longest path between any two nodes, measured in edges — and that path does not have to pass through the root.

Think of it as

At every node, the longest path THROUGH that node is left-height + right-height + 2 (the two edges connecting the node to each subtree's deepest point). The diameter is the maximum of that quantity over every node — computed alongside height in one bottom-up pass, so nothing is recomputed twice.

What we're doing: Find a binary tree's diameter by tracking the best left-height + right-height + 2 seen during a single height computation.

diameter.pypython

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


def diameter(root):
    best = [0]

    def height(node):
        if node is None:
            return -1
        left_h = height(node.left)
        right_h = height(node.right)
        best[0] = max(best[0], left_h + right_h + 2)
        return 1 + max(left_h, right_h)

    height(root)
    return best[0]


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(diameter(root))

10: best is a one-element list, not a plain variable, so the nested height() closure can mutate it — a plain int would need nonlocal instead.
12: Every node updates best using its OWN left/right heights — the diameter check happens at every node, not just the root.

Output

Why this works: The longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) — 3 edges. That maximum is found at the root, where left_h (height of the 2-subtree) is 1 and right_h (height of the 3-subtree) is 0, giving 1 + 0 + 2 = 3 — larger than any single subtree could report on its own.

Remember: Track the best left-height + right-height + 2 seen at ANY node while computing height in one pass — the longest path does not have to run through the root.

Was this helpful?

Checking if a tree is balanced

standardintermediate

A tree is height-balanced if, at EVERY node, the heights of its left and right subtrees differ by at most 1 — not just at the root.

Think of it as

A naive check recomputes height from scratch at every node to compare its two sides — O(n) work at each of n nodes, O(n²) total. The efficient version computes height bottom-up once, and the moment any node fails the balance test, short-circuits by returning a sentinel (-1) that propagates straight up, skipping every remaining comparison.

What we're doing: Check whether a balanced tree and a deliberately lopsided one are height-balanced.

is_balanced.pypython

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


def is_balanced(root):
    def check(node):
        if node is None:
            return 0
        left_h = check(node.left)
        if left_h == -1:
            return -1
        right_h = check(node.right)
        if right_h == -1:
            return -1
        if abs(left_h - right_h) > 1:
            return -1
        return 1 + max(left_h, right_h)

    return check(root) != -1


balanced = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
unbalanced = TreeNode(1, TreeNode(2, TreeNode(4, TreeNode(5))), None)

print(is_balanced(balanced))
print(is_balanced(unbalanced))

13: The moment a subtree reports -1 (already unbalanced somewhere below), this branch stops immediately and never bothers computing the other side.
16: The actual balance test — if the two sides differ by more than 1, this node itself fails, regardless of how balanced its own children are.

Output

True
False

Why this works: balanced never has a height gap greater than 1 at any node. unbalanced has a 4-node chain (1 → 2 → 4 → 5) down its left side with nothing on the right at node 2 — the gap between that side's height and the missing right side exceeds 1, so check() returns -1, and is_balanced correctly reports False.

Remember: Balance must hold at EVERY node, not just the root — compute height bottom-up and short-circuit to a sentinel the instant any node fails, instead of recomputing height from scratch at each one.

Was this helpful?

Serializing/deserializing a binary tree (conceptually)

referenceintermediate

Serializing turns a tree into a flat, linear representation — a string or list — that can be sent over a network or written to disk. Deserializing reconstructs the exact same tree from that representation. Preorder traversal, with an explicit marker for "no child here", is the standard approach.

What we're doing: Serialize a small tree into a flat list, using "#" as the missing-child marker.

serialize.pypython

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


def serialize(node):
    if node is None:
        return ['#']
    return [str(node.value)] + serialize(node.left) + serialize(node.right)


root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4)))
print(serialize(root))

8: A missing child is not skipped — it is recorded as '#', which is exactly what lets deserializing know where a subtree ends.
9: Preorder order: the node's own value first, so a reader consuming left to right always sees a subtree's root before its children.

Output

['1', '2', '#', '#', '3', '4', '#', '#', '#']

Why this works: Node 1 is written first, then its whole left subtree (2, with two missing children), then its whole right subtree (3, with left child 4). Every leaf contributes two trailing "#" markers — one for each missing child — which is what makes this list enough to rebuild the tree exactly, not just list its values.

Remember: An explicit null marker is what makes a traversal reversible — without one, two different trees can produce the exact same list of values.

N-ary trees (brief awareness)

referencebeginner

An n-ary tree lets each node have any number of children, stored as a list, instead of the two a binary tree allows — a file system or an org chart is a natural n-ary tree, where a binary tree would be an awkward fit.

nary_tree.pypython

class NaryNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


root = NaryNode(1, [NaryNode(2), NaryNode(3), NaryNode(4)])

Remember: A binary tree is just an n-ary tree capped at 2 children — the moment a node can have three or more children, reach for a children list, not named left/right fields.