The Complete Tree Crash Course

1. Root

The topmost node, the only one with no parent.

Every traversal starts here. In this tree the root is 5.

2. Leaf

A node with no children.

1, 4 and 9 are the leaves of this tree.

3. Child

A node directly below another node.

3 and 8 are children of 5. A binary tree node has at most two.

4. Subtree

Any node together with everything below it.

The subtree rooted at 3 holds 3, 1 and 4, and is itself a tree.

5. Height

The number of edges on the longest path from a node down to a leaf.

Leaves have height 0, and the root here has height 2.

6. Depth

The number of edges from the root down to a node.

The root has depth 0, and 9 has depth 2.

7. Ancestor

Any node on the path from a node up to the root.

5 and 8 are the ancestors of 9.

8. Descendant

Any node in a node's subtree, below the node itself.

1 and 4 are the descendants of 3.

Building a Node

A binary tree node holds a value and links to a left and a right child.

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

Problems usually hand you the root node only.

From any node, node.left and node.right lead to its children, and node.val holds its value.

A missing child is None, which is the base case of most recursive tree functions.

Depth First Search

Goes deep along one branch before backing up. The three orders only differ in when the current node is processed.

• Preorder: node, left, right
• Inorder: left, node, right
• Postorder: left, right, node

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)   # move this line for pre or post
    inorder(node.right)

Breadth First Search

Processes the tree one level at a time. Also called level order traversal.

from collections import deque

def level_order(root):
    queue = deque([root] if root else [])
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            print(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

Iterative DFS

Any recursive traversal can be rewritten with your own stack. Here is inorder:

def inorder(root):
    stack, node = [], root
    while stack or node:
        while node:            # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)        # visit
        node = node.right      # then the right subtree

Preorder is even simpler: pop a node, visit it, then push its right child and its left child.

Interviewers often ask for this version once your recursive answer works.

Binary Search Tree

A binary tree that keeps its values in order.

Everything in the left subtree is smaller than the node, and everything in the right subtree is larger.

Most interview versions assume the values are unique.

Operations to know:

• Search
• Insert
• Delete a node with zero, one or two children
• Inorder traversal gives sorted order

Full Binary Tree

• Every node has either zero or two children
• No node has exactly one child

Complete Binary Tree

• Every level is full except possibly the last
• The last level fills from left to right

Perfect Binary Tree

• Every internal node has two children
• All leaves sit on the same level

Balanced Binary Tree

• For every node, the heights of its two subtrees differ by at most one

Degenerate Binary Tree

• Every parent has exactly one child
• It behaves like a linked list, so its height is O(n)

Heaps

A complete binary tree with one ordering rule: in a min heap every parent is smaller than or equal to its children.

It gives you the smallest element in O(1) and removes it in O(log n), which is why heaps power priority queues.

Because the tree is complete, it is stored in a plain array: the children of index i live at 2i + 1 and 2i + 2.

N-ary Trees

Nodes can have any number of children, stored as a list. File systems and comment threads look like this.

Traversals work the same way, except you loop over every child instead of visiting left and right.

def dfs(node):
    for child in node.children:
        dfs(child)

Trie (Prefix Tree)

Each node stands for one character, and the path from the root spells a prefix.

Looking up a word or a prefix takes time proportional to its length, no matter how many words are stored.

Green nodes end a word: cat, car and dog.

Tries are the go-to structure for autocomplete and word search problems.

Segment Trees

Each node stores a summary, such as the sum, of a range of an array. The root covers the whole array and each child covers half of its parent.

Range queries and single updates both take O(log n).

Rare in interviews, but worth recognizing when a problem mixes range queries with updates.