Paths and lowest common ancestors

What is a binary tree?

A tree connects nodes in a hierarchy. The root is its starting node. A child is directly below its parent; a leaf has no children. A binary tree allows at most two children per node, called left and right. Traversal means visiting its nodes in a defined order.

Example: A root containing 8 can have a left child 4 and a right child 12. A binary tree does not automatically keep smaller values on the left: that extra rule belongs to a binary search tree.

Helpful before this chapter

If these ideas are new, begin with:

Queues and deques Recursion

Understand the idea

Paths preserve ancestor relationships. In a general tree, lowest common ancestor is the deepest node whose subtree contains both targets. Node identity matters when values repeat; missing targets need a defined policy.

Work through an example

Targets 1 and 3 have LCA 2; targets 1 and 6 have LCA 4. Two nonempty child results indicate a split at the current node.

Time and space complexity

O(n) time/O(h) stack for general-tree LCA; path output adds O(h).

Why it works

A returned candidate summarizes target presence or the already found ancestor within that subtree.

Common mistakes

A standard candidate-returning algorithm assumes both targets exist.
Values alone may not identify nodes.

Chapter lab · Python implementation

A tree gives each non-root node one parent and contains no cycles. Our binary-tree lab combines inorder traversal, subtree height, and explicit-null serialization. Height counts edges here: empty=-1, leaf=0. Some practice problems count nodes instead; translate the convention rather than changing the recurrence blindly.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def inorder(node):
    if node is None: return []
    return inorder(node.left)+[node.value]+inorder(node.right)

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

def serialize(node):
    tokens=[]
    def visit(n):
        if n is None:
            tokens.append(None); return
        tokens.append(n.value)
        visit(n.left); visit(n.right)
    visit(node)
    return tokens

def deserialize(tokens):
    stream=iter(tokens)
    def build():
        value=next(stream)
        if value is None: return None
        return Node(value,build(),build())
    root=build()
    sentinel=object()
    if next(stream,sentinel) is not sentinel:
        raise ValueError('extra tokens')
    return root

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=Node(4,Node(2,Node(1),Node(3)),Node(6))
assert inorder(root)==[1,2,3,4,6]
assert height(root)==2 and height(None)==-1
assert serialize(deserialize(serialize(root)))==serialize(root)
assert serialize(None)==[None]

CHECK YOUR UNDERSTANDING