Building trees

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

Construction needs enough information to identify both structure and values. Preorder plus inorder can uniquely build a binary tree when values are distinct; root position in inorder separates child regions.

Work through an example

Preorder [4,2,1,3,6], inorder [1,2,3,4,6]: root is 4; left inorder is [1,2,3], right [6]. Advance one preorder cursor through recursive ranges.

Time and space complexity

O(n) with an inorder-index map/O(n) map and stack; repeated scans can be O(n²).

Why it works

Each call consumes the preorder root of its specified inorder segment.

Common mistakes

Duplicate values destroy simple uniqueness.
Input traversals must describe the same tree.

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